Submission #1264424

#TimeUsernameProblemLanguageResultExecution timeMemory
1264424ArtParachute rings (IOI12_rings)C++20
100 / 100
680 ms94184 KiB
// - Art - #include <bits/stdc++.h> #define el cout << '\n' #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define REV(i, b, a) for (int i = (b), _a = (a); i >= _a; --i) #define REP(i, c) for (int i = 0, _c = (c); i < _c; ++i) const int N = 1e6 + 7; using namespace std; struct DisjointSet { vector<int> lab; DisjointSet(int n = 0) { lab.assign(n + 1, -1); } int findSet(int x) { return lab[x] < 0 ? x : lab[x] = findSet(lab[x]); } bool unionSet(int x, int y) { x = findSet(x), y = findSet(y); if (x == y) { return false; } if (lab[x] > lab[y]) swap(x, y); lab[x] += lab[y]; lab[y] = x; return true; } int getSize(int x) { return -lab[findSet(x)]; } }; struct Graph { vector<int> deg; int n, delNode; int szCycle; // 0 = no cycle, -1 = more than one cycle bool deg3; DisjointSet dsu; Graph() { n = delNode = szCycle = 0; deg3 = false; } Graph(int _n, int _delNode) { n = _n; delNode = _delNode; szCycle = 0; deg3 = false; deg.assign(n + 1, 0); dsu = DisjointSet(n); } void addEdge(int u, int v) { if (u == delNode || v == delNode) { return; } if (++deg[u] >= 3) { deg3 = true; } if (++deg[v] >= 3) { deg3 = true; } if (!dsu.unionSet(u, v)) { // u, v already in same set int sz = dsu.getSize(u); if (szCycle == 0) { szCycle = sz; } else { szCycle = -1; } } } bool isValid() { return !deg3 && !szCycle; } int calc() { if (szCycle == -1) { return 0; } return !szCycle ? n : szCycle; } } whole, rem[4]; int n; vector<int> adj[N]; int pharse = 1; void Init(int _n) { n = _n; whole = Graph(_n, -1); } void Link(int u, int v) { ++u; ++v; adj[u].emplace_back(v); adj[v].emplace_back(u); if (pharse == 1) { if (adj[u].size() == 3 || adj[v].size() == 3) { int tmp = adj[u].size() == 3 ? u : v; rem[0] = Graph(n, tmp); rem[1] = Graph(n, adj[tmp][0]); rem[2] = Graph(n, adj[tmp][1]); rem[3] = Graph(n, adj[tmp][2]); FOR (u, 1, n) for (int &v : adj[u]) if (u < v) { REP (i, 4) { rem[i].addEdge(u, v); } } pharse = 2; } else { whole.addEdge(u, v); } } else { REP (i, 4) { rem[i].addEdge(u, v); } } } int CountCritical() { if (pharse == 1) { return whole.calc(); } int res = 0; REP (i, 4) { res += rem[i].isValid(); } return res; } #ifdef ONLINE_JUDGE int main() { #define name "art" if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // int subtask; // cin >> subtask; int n, q; cin >> n >> q; Init(n); FOR (i, 1, q) { int u, v; cin >> u; if (u == -1) { cout << CountCritical(), el; } else { cin >> v; Link(u, v); } } return 0; } #endif // ONLINE_JUDGE
#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...