This documentation is automatically generated by online-judge-tools/verification-helper
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3198
#include "../../template/template.hpp"
#include "../../graph/flow/bipartite-flow.hpp"
int main() {
int N, M, Q;
cin >> N >> M;
BipartiteFlow flow(N, N);
set< pair< int, int > > mas;
for(int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
--a, --b;
mas.emplace(a, b);
flow.add_edge(a, b);
}
cin >> Q;
while(Q--) {
int a, b;
cin >> a >> b;
--a, --b;
if(mas.count({a, b})) {
mas.erase({a, b});
flow.erase_edge(a, b);
} else {
mas.emplace(a, b);
flow.add_edge(a, b);
}
if(flow.max_matching().size() == N) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
#line 1 "test/verify/aoj-3198.test.cpp"
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3198
#line 1 "template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
os << p.first << " " << p.second;
return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &in : v) is >> in;
return is;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
return a < b && (a = b, true);
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
return a > b && (a = b, true);
}
template <typename T = int64>
vector<T> make_v(size_t a) {
return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
for (auto &e : t) fill_v(e, v);
}
template <typename F>
struct FixPoint : F {
explicit FixPoint(F &&f) : F(forward<F>(f)) {}
template <typename... Args>
decltype(auto) operator()(Args &&...args) const {
return F::operator()(*this, forward<Args>(args)...);
}
};
template <typename F>
inline decltype(auto) MFP(F &&f) {
return FixPoint<F>{forward<F>(f)};
}
#line 4 "test/verify/aoj-3198.test.cpp"
#line 1 "graph/flow/bipartite-flow.hpp"
/**
* @brief Bipartite Flow(二部グラフのフロー)
*
*/
struct BipartiteFlow {
size_t n, m, time_stamp;
vector<vector<int> > g, rg;
vector<int> match_l, match_r, dist, used, alive;
bool matched;
public:
explicit BipartiteFlow(size_t n, size_t m)
: n(n),
m(m),
time_stamp(0),
g(n),
rg(m),
match_l(n, -1),
match_r(m, -1),
used(n),
alive(n, 1),
matched(false) {}
void add_edge(int u, int v) {
g[u].push_back(v);
rg[v].emplace_back(u);
}
vector<pair<int, int> > max_matching() {
matched = true;
for (;;) {
build_augment_path();
++time_stamp;
int flow = 0;
for (int i = 0; i < (int)n; i++) {
if (match_l[i] == -1) flow += find_min_dist_augment_path(i);
}
if (flow == 0) break;
}
vector<pair<int, int> > ret;
for (int i = 0; i < (int)n; i++) {
if (match_l[i] >= 0) ret.emplace_back(i, match_l[i]);
}
return ret;
}
/* http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3198 */
void erase_edge(int a, int b) {
if (match_l[a] == b) {
match_l[a] = -1;
match_r[b] = -1;
}
g[a].erase(find(begin(g[a]), end(g[a]), b));
rg[b].erase(find(begin(rg[b]), end(rg[b]), a));
}
/* http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0334 */
vector<pair<int, int> > lex_max_matching() {
if (!matched) max_matching();
for (auto &vs : g) sort(begin(vs), end(vs));
vector<pair<int, int> > es;
for (int i = 0; i < (int)n; i++) {
if (match_l[i] == -1 || alive[i] == 0) {
continue;
}
match_r[match_l[i]] = -1;
match_l[i] = -1;
++time_stamp;
find_augment_path(i);
alive[i] = 0;
es.emplace_back(i, match_l[i]);
}
return es;
}
vector<int> min_vertex_cover() {
auto visited = find_residual_path();
vector<int> ret;
for (int i = 0; i < (int)(n + m); i++) {
if (visited[i] ^ (i < (int)n)) {
ret.emplace_back(i);
}
}
return ret;
}
/* https://atcoder.jp/contests/utpc2013/tasks/utpc2013_11 */
vector<int> lex_min_vertex_cover(const vector<int> &ord) {
assert(ord.size() == n + m);
auto res = build_risidual_graph();
vector<vector<int> > r_res(n + m + 2);
for (int i = 0; i < (int)(n + m + 2); i++) {
for (auto &j : res[i]) r_res[j].emplace_back(i);
}
queue<int> que;
vector<int> visited(n + m + 2, -1);
auto expand_left = [&](int t) {
if (visited[t] != -1) return;
que.emplace(t);
visited[t] = 1;
while (!que.empty()) {
int idx = que.front();
que.pop();
for (auto &to : r_res[idx]) {
if (visited[to] != -1) continue;
visited[to] = 1;
que.emplace(to);
}
}
};
auto expand_right = [&](int t) {
if (visited[t] != -1) return;
que.emplace(t);
visited[t] = 0;
while (!que.empty()) {
int idx = que.front();
que.pop();
for (auto &to : res[idx]) {
if (visited[to] != -1) continue;
visited[to] = 0;
que.emplace(to);
}
}
};
expand_right(n + m);
expand_left(n + m + 1);
vector<int> ret;
for (auto &t : ord) {
if (t < (int)n) {
expand_left(t);
if (visited[t] & 1) ret.emplace_back(t);
} else {
expand_right(t);
if (~visited[t] & 1) ret.emplace_back(t);
}
}
return ret;
}
vector<int> max_independent_set() {
auto visited = find_residual_path();
vector<int> ret;
for (int i = 0; i < (int)(n + m); i++) {
if (visited[i] ^ (i >= (int)n)) {
ret.emplace_back(i);
}
}
return ret;
}
vector<pair<int, int> > min_edge_cover() {
auto es = max_matching();
for (int i = 0; i < (int)n; i++) {
if (match_l[i] >= 0) {
continue;
}
if (g[i].empty()) {
return {};
}
es.emplace_back(i, g[i][0]);
}
for (int i = 0; i < (int)m; i++) {
if (match_r[i] >= 0) {
continue;
}
if (rg[i].empty()) {
return {};
}
es.emplace_back(rg[i][0], i);
}
return es;
}
// left: [0,n), right: [n,n+m), S: n+m, T: n+m+1
vector<vector<int> > build_risidual_graph() {
if (!matched) max_matching();
const size_t S = n + m;
const size_t T = n + m + 1;
vector<vector<int> > ris(n + m + 2);
for (int i = 0; i < (int)n; i++) {
if (match_l[i] == -1)
ris[S].emplace_back(i);
else
ris[i].emplace_back(S);
}
for (int i = 0; i < (int)m; i++) {
if (match_r[i] == -1)
ris[i + n].emplace_back(T);
else
ris[T].emplace_back(i + n);
}
for (int i = 0; i < (int)n; i++) {
for (auto &j : g[i]) {
if (match_l[i] == j)
ris[j + n].emplace_back(i);
else
ris[i].emplace_back(j + n);
}
}
return ris;
}
private:
vector<int> find_residual_path() {
auto res = build_risidual_graph();
queue<int> que;
vector<int> visited(n + m + 2);
que.emplace(n + m);
visited[n + m] = true;
while (!que.empty()) {
int idx = que.front();
que.pop();
for (auto &to : res[idx]) {
if (visited[to]) continue;
visited[to] = true;
que.emplace(to);
}
}
return visited;
}
void build_augment_path() {
queue<int> que;
dist.assign(g.size(), -1);
for (int i = 0; i < (int)n; i++) {
if (match_l[i] == -1) {
que.emplace(i);
dist[i] = 0;
}
}
while (!que.empty()) {
int a = que.front();
que.pop();
for (auto &b : g[a]) {
int c = match_r[b];
if (c >= 0 && dist[c] == -1) {
dist[c] = dist[a] + 1;
que.emplace(c);
}
}
}
}
bool find_min_dist_augment_path(int a) {
used[a] = time_stamp;
for (auto &b : g[a]) {
int c = match_r[b];
if (c < 0 || (used[c] != (int)time_stamp && dist[c] == dist[a] + 1 &&
find_min_dist_augment_path(c))) {
match_r[b] = a;
match_l[a] = b;
return true;
}
}
return false;
}
bool find_augment_path(int a) {
used[a] = time_stamp;
for (auto &b : g[a]) {
int c = match_r[b];
if (c < 0 || (alive[c] == 1 && used[c] != (int)time_stamp &&
find_augment_path(c))) {
match_r[b] = a;
match_l[a] = b;
return true;
}
}
return false;
}
};
#line 6 "test/verify/aoj-3198.test.cpp"
int main() {
int N, M, Q;
cin >> N >> M;
BipartiteFlow flow(N, N);
set< pair< int, int > > mas;
for(int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
--a, --b;
mas.emplace(a, b);
flow.add_edge(a, b);
}
cin >> Q;
while(Q--) {
int a, b;
cin >> a >> b;
--a, --b;
if(mas.count({a, b})) {
mas.erase({a, b});
flow.erase_edge(a, b);
} else {
mas.emplace(a, b);
flow.add_edge(a, b);
}
if(flow.max_matching().size() == N) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | 00_sample01 | AC | 8 ms | 4 MB |
g++ | 01_small_random_01 | AC | 8 ms | 4 MB |
g++ | 01_small_random_02 | AC | 8 ms | 4 MB |
g++ | 01_small_random_03 | AC | 10 ms | 4 MB |
g++ | 01_small_random_04 | AC | 9 ms | 4 MB |
g++ | 01_small_random_05 | AC | 10 ms | 4 MB |
g++ | 01_small_random_06 | AC | 8 ms | 4 MB |
g++ | 01_small_random_07 | AC | 8 ms | 4 MB |
g++ | 01_small_random_08 | AC | 9 ms | 4 MB |
g++ | 01_small_random_09 | AC | 8 ms | 4 MB |
g++ | 01_small_random_10 | AC | 8 ms | 4 MB |
g++ | 02_random_01 | AC | 15 ms | 4 MB |
g++ | 02_random_02 | AC | 17 ms | 4 MB |
g++ | 02_random_03 | AC | 21 ms | 4 MB |
g++ | 02_random_04 | AC | 140 ms | 4 MB |
g++ | 02_random_05 | AC | 75 ms | 4 MB |
g++ | 02_random_06 | AC | 96 ms | 5 MB |
g++ | 02_random_07 | AC | 56 ms | 4 MB |
g++ | 02_random_08 | AC | 18 ms | 4 MB |
g++ | 02_random_09 | AC | 112 ms | 4 MB |
g++ | 02_random_10 | AC | 68 ms | 4 MB |
g++ | 03_max_00 | AC | 301 ms | 5 MB |
g++ | 03_max_01 | AC | 18 ms | 4 MB |
g++ | 04_random_plus_01 | AC | 26 ms | 4 MB |
g++ | 04_random_plus_02 | AC | 24 ms | 4 MB |
g++ | 04_random_plus_03 | AC | 19 ms | 4 MB |
g++ | 04_random_plus_04 | AC | 21 ms | 4 MB |
g++ | 04_random_plus_05 | AC | 14 ms | 4 MB |
g++ | 04_random_plus_06 | AC | 8 ms | 4 MB |
g++ | 04_random_plus_07 | AC | 21 ms | 4 MB |
g++ | 04_random_plus_08 | AC | 30 ms | 4 MB |
g++ | 04_random_plus_09 | AC | 34 ms | 4 MB |
g++ | 04_random_plus_10 | AC | 21 ms | 4 MB |
clang++ | 00_sample01 | AC | 7 ms | 4 MB |
clang++ | 01_small_random_01 | AC | 8 ms | 4 MB |
clang++ | 01_small_random_02 | AC | 8 ms | 4 MB |
clang++ | 01_small_random_03 | AC | 9 ms | 4 MB |
clang++ | 01_small_random_04 | AC | 8 ms | 4 MB |
clang++ | 01_small_random_05 | AC | 10 ms | 4 MB |
clang++ | 01_small_random_06 | AC | 8 ms | 4 MB |
clang++ | 01_small_random_07 | AC | 8 ms | 4 MB |
clang++ | 01_small_random_08 | AC | 10 ms | 4 MB |
clang++ | 01_small_random_09 | AC | 7 ms | 4 MB |
clang++ | 01_small_random_10 | AC | 8 ms | 4 MB |
clang++ | 02_random_01 | AC | 14 ms | 4 MB |
clang++ | 02_random_02 | AC | 17 ms | 4 MB |
clang++ | 02_random_03 | AC | 21 ms | 4 MB |
clang++ | 02_random_04 | AC | 151 ms | 4 MB |
clang++ | 02_random_05 | AC | 74 ms | 4 MB |
clang++ | 02_random_06 | AC | 88 ms | 5 MB |
clang++ | 02_random_07 | AC | 54 ms | 4 MB |
clang++ | 02_random_08 | AC | 17 ms | 4 MB |
clang++ | 02_random_09 | AC | 103 ms | 4 MB |
clang++ | 02_random_10 | AC | 65 ms | 4 MB |
clang++ | 03_max_00 | AC | 284 ms | 5 MB |
clang++ | 03_max_01 | AC | 17 ms | 4 MB |
clang++ | 04_random_plus_01 | AC | 24 ms | 4 MB |
clang++ | 04_random_plus_02 | AC | 22 ms | 4 MB |
clang++ | 04_random_plus_03 | AC | 18 ms | 4 MB |
clang++ | 04_random_plus_04 | AC | 20 ms | 4 MB |
clang++ | 04_random_plus_05 | AC | 13 ms | 4 MB |
clang++ | 04_random_plus_06 | AC | 8 ms | 4 MB |
clang++ | 04_random_plus_07 | AC | 19 ms | 4 MB |
clang++ | 04_random_plus_08 | AC | 28 ms | 4 MB |
clang++ | 04_random_plus_09 | AC | 31 ms | 4 MB |
clang++ | 04_random_plus_10 | AC | 20 ms | 4 MB |