Submission #1111726

#TimeUsernameProblemLanguageResultExecution timeMemory
1111726vjudge1Parachute rings (IOI12_rings)C++17
17 / 100
770 ms119408 KiB
#include <bits/stdc++.h> using namespace std; #define synchronize {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);} #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } #define ll long long #define pii pair<int, int> #define fi first #define se second const int nmax = 1e6 + 5; int theta, n, q; int u, v, cyc, res; bool check = false; int par[nmax], sz[nmax], deg[nmax]; vector<pii> edges; vector<int> adj[nmax]; struct DSU { int root, ans; vector<int> par, deg; DSU() { ans = 1; root = 0; par.resize(nmax + 1); deg.resize(nmax + 1); for (int i = 1; i <= nmax; i++) { par[i] = i; deg[i] = 0; } } void init() { ans = 1; for (int i = 1; i <= n; i++) { par[i] = i; // deg[i] = 0; } for (auto [u, v] : edges) { merge(u, v); } } int find(int u) { if (u == par[u]) return u; return par[u] = find(par[u]); } void merge(int u, int v) { if (u == root || v == root || ans == 0) return; if (++deg[u] == 3) ans = 0; if (++deg[v] == 3) ans = 0; u = find(u), v = find(v); if (u == v) { ans = 0; return; } par[u] = v; } } ds[4]; int find(int u) { if (u == par[u]) return u; return par[u] = find(par[u]); } void Init(int _n) { n = _n; for (int i = 1; i <= n; i++) { par[i] = i; deg[i] = 0; sz[i] = 1; } } void Link(int u, int v) { if (check) { for (int i = 0; i < 4; i++) ds[i].merge(u, v); return; } edges.push_back({u, v}); adj[u].push_back(v); adj[v].push_back(u); if (deg[u] == 2 || deg[v] == 2) check = true; if (++deg[u] == 3) { ds[0].root = u; for (int i = 1; i < 4; i++) ds[i].root = adj[u][i - 1]; for (int i = 0; i < 4; i++) ds[i].init(); return; } if (++deg[v] == 3) { ds[0].root = v; for (int i = 1; i < 4; i++) ds[i].root = adj[v][i - 1]; for (int i = 0; i < 4; i++) ds[i].init(); return; } u = find(u), v = find(v); if (u == v) { res = sz[u]; cyc++; } else { sz[u] += sz[v]; par[v] = u; } } int CountCritical() { if (cyc > 1) return 0; if (check) return ds[0].ans + ds[1].ans + ds[2].ans + ds[3].ans; if (cyc == 1) return res; return n; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...