Submission #252565

#TimeUsernameProblemLanguageResultExecution timeMemory
252565KubinParachute rings (IOI12_rings)C++17
0 / 100
4086 ms61588 KiB
#include <bits/stdc++.h> using namespace std; struct disjoint_sets { vector<size_t> repr, rank; disjoint_sets(size_t n) : repr(n), rank(n) { for(size_t i = 0; i < n; i++) repr[i] = i; } size_t find(size_t v) { return v == repr[v] ? v : repr[v] = find(repr[v]); } bool unite(size_t u, size_t v) { if((u = find(u)) == (v = find(v))) return false; if(rank[u] > rank[v]) swap(u, v); rank[v] += (rank[u] == rank[v]); repr[u] = v; return true; } }; enum BambooForestStatus { Ok, Cycles, Bad }; struct bamboo_forest { BambooForestStatus status = Ok; disjoint_sets dsets; vector<size_t> deg; size_t cycles = 0; bamboo_forest(size_t n) : dsets(n), deg(n) {} bamboo_forest() : bamboo_forest(0) {} BambooForestStatus edge(size_t u, size_t v) { deg[u]++; deg[v]++; if(deg[u] > 2 or deg[v] > 2) status = Bad; if((status == Ok or status == Cycles) and dsets.find(u) == dsets.find(v) and deg[u] == 2 and deg[v] == 2) status = Cycles, cycles++; else if(not dsets.unite(u, v)) status = Bad; return status; } }; size_t n; vector<pair<size_t, size_t>> edges; vector<vector<size_t>> graph; bamboo_forest base; size_t first_cycle_size; unordered_set<size_t> major; void Init(int _n) { n = _n; base = bamboo_forest(n); graph.resize(n); } void Link(int u, int v) { edges.emplace_back(u, v); graph[u].push_back(v); graph[v].push_back(u); auto pre = base.status; base.edge(u, v); /* if(pre == Ok and base.status == Cycles and base.cycles == 1) { auto w = base.dsets.find(u); for(size_t i = 0; i < n; i++) if(base.dsets.find(i) == w) first_cycle_size++; } if(base.deg[u] > 2) major.insert(u); if(base.deg[v] > 2) major.insert(v); */ } int CountCritical() { /* if(base.status == Ok) return n; else if(base.status == Cycles and base.cycles == 1) return first_cycle_size; else if(base.status == Cycles and base.cycles > 1) return 0; else */ { size_t result = 0; for(size_t i = 0; i < n; i++) { bamboo_forest re(n); for(auto [u, v] : edges) re.edge(u, v); result += re.status == Ok; } return result; } }

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:82:10: warning: unused variable 'pre' [-Wunused-variable]
     auto pre = base.status;
          ^~~
#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...