#define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) constexpr int MAX_N = 4096; int n, numMatches, cnt; bool st[MAX_N][MAX_N]; Pii match[MAX_N][MAX_N]; int seen[MAX_N][MAX_N]; void print() { rep(i, 0, n) { rep(j, 0, n) { cerr << st[i][j] << ' '; } cerr << '\n'; } } int augment(int i, int j) { if (seen[i][j] == cnt) return 0; seen[i][j] = cnt; rep(k, 0, n) { if (st[i][j] != st[i][k] && (match[i][k].x < 0 || augment(match[i][k].x, match[i][k].y))) { match[i][j] = {i, k}; match[i][k] = {i, j}; return 1; } if (st[i][j] != st[k][j] && (match[k][j].x < 0 || augment(match[k][j].x, match[k][j].y))) { match[i][j] = {k, j}; match[k][j] = {i, j}; return 1; } } return 0; } void turbo() { rep(i, 0, n) { rep(j, 0, n) { match[i][j] = {-1, -1}; } } int k = 1; while (k) { cnt++; k = 0; rep(i, 0, n) { rep(j, 0, n) { if (match[i][j].x < 0) { k += augment(i, j); } } } numMatches += k; } } int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int m, q; cin >> n >> m >> q; rep(i, 0, m) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; x1--; y1--; st[x1][y1] ^= 1; st[x2][y1] ^= 1; st[x1][y2] ^= 1; st[x2][y2] ^= 1; } rep(i, 0, n+5) rep(j, 1, n+5) st[i][j] ^= st[i][j-1]; rep(i, 0, n+5) rep(j, 1, n+5) st[j][i] ^= st[j-1][i]; turbo(); cout << numMatches << '\n'; rep(i, 0, q) { int a, b; cin >> a >> b; a--; b--; st[a][b] ^= 1; if (match[a][b].x != -1) { int c = match[a][b].x, d = match[a][b].y; match[a][b] = {-1, -1}; match[c][d] = {-1, -1}; numMatches--; cnt++; numMatches += augment(c, d); } cnt++; numMatches += augment(a, b); cout << numMatches << '\n'; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | #define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) constexpr int MAX_N = 4096; int n, numMatches, cnt; bool st[MAX_N][MAX_N]; Pii match[MAX_N][MAX_N]; int seen[MAX_N][MAX_N]; void print() { rep(i, 0, n) { rep(j, 0, n) { cerr << st[i][j] << ' '; } cerr << '\n'; } } int augment(int i, int j) { if (seen[i][j] == cnt) return 0; seen[i][j] = cnt; rep(k, 0, n) { if (st[i][j] != st[i][k] && (match[i][k].x < 0 || augment(match[i][k].x, match[i][k].y))) { match[i][j] = {i, k}; match[i][k] = {i, j}; return 1; } if (st[i][j] != st[k][j] && (match[k][j].x < 0 || augment(match[k][j].x, match[k][j].y))) { match[i][j] = {k, j}; match[k][j] = {i, j}; return 1; } } return 0; } void turbo() { rep(i, 0, n) { rep(j, 0, n) { match[i][j] = {-1, -1}; } } int k = 1; while (k) { cnt++; k = 0; rep(i, 0, n) { rep(j, 0, n) { if (match[i][j].x < 0) { k += augment(i, j); } } } numMatches += k; } } int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int m, q; cin >> n >> m >> q; rep(i, 0, m) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; x1--; y1--; st[x1][y1] ^= 1; st[x2][y1] ^= 1; st[x1][y2] ^= 1; st[x2][y2] ^= 1; } rep(i, 0, n+5) rep(j, 1, n+5) st[i][j] ^= st[i][j-1]; rep(i, 0, n+5) rep(j, 1, n+5) st[j][i] ^= st[j-1][i]; turbo(); cout << numMatches << '\n'; rep(i, 0, q) { int a, b; cin >> a >> b; a--; b--; st[a][b] ^= 1; if (match[a][b].x != -1) { int c = match[a][b].x, d = match[a][b].y; match[a][b] = {-1, -1}; match[c][d] = {-1, -1}; numMatches--; cnt++; numMatches += augment(c, d); } cnt++; numMatches += augment(a, b); cout << numMatches << '\n'; } return 0; } |