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
| #include <bits/stdc++.h> using std::cerr; using std::endl;
inline int rd() { int b = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) b = b * 10 + c - '0', c = getchar(); return b; }
const int N = 2600;
int n, m, s, t, sum, ins[N]; int deg[N];
struct Edge { int x, y; }; std::vector<Edge> E[N];
int fa[N], Fa[N]; int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
inline int solve() { deg[s] ^= 1, deg[t] ^= 1; ++ins[s], ++ins[t]; for (int i = 1; i <= n; ++i) { fa[i] = Fa[i]; E[i].clear(); } int ret = sum; for (int i = 1, j = 0; i <= n; ++i) { if (!(deg[i] & 1)) continue; if (!j) j = i; else { for (int k = j; k < i; ++k) { int x = find(k), y = find(k + 1); fa[x] = y; } ret += i - j, j = 0; } } for (int i = 1, j = 2; i <= n; ++i) { if (!ins[i]) continue; if (j <= i) j = i + 1; while (j <= n && (!ins[j] find(j) == find(i))) ++j; if (j <= n) E[j - i].push_back({ i, j }); else break; } for (int i = 1; i <= n; ++i) for (auto e : E[i]) { int x = find(e.x), y = find(e.y); if (x != y) { fa[x] = y, ret += 2 * i; } } deg[s] ^= 1, deg[t] ^= 1; --ins[s], --ins[t]; return ret; }
int main() { n = rd(), m = rd(), s = rd(); for (int i = 1; i <= n; ++i) fa[i] = i; for (int i = 1; i <= m; ++i) { int x = rd(), y = rd(); sum += std::abs(x - y); deg[x] ^= 1, deg[y] ^= 1; ++ins[x], ++ins[y]; x = find(x), y = find(y); if (x != y) fa[x] = y; } for (int i = 1; i <= n; ++i) Fa[i] = fa[i]; for (t = 1; t <= n; ++t) printf("%d ", solve()); putchar('\n'); return 0; }
|