Submission #290973

#TimeUsernameProblemLanguageResultExecution timeMemory
290973stoyan_malininParachute rings (IOI12_rings)C++14
0 / 100
551 ms262144 KiB
//#include "grader.cpp" #include <set> #include <map> #include <vector> #include <cstring> #include <iostream> #include <algorithm> #include <functional> using namespace std; const int MAXN = 1500; struct Graph { struct DSU { int n; int deg[MAXN]; int parent[MAXN], treeSize[MAXN]; bool isBad[MAXN]; int badComponentSz; int components, badComponents; DSU(){} DSU(int n) { this->n = n; this->components = n; this->badComponents = 0; for(int i = 0;i<n;i++) { this->deg[i] = 0; this->parent[i] = i; this->treeSize[i] = 1; this->isBad[i] = false; } } int Find(int x) { if(parent[x]==x) return x; parent[x] = Find(parent[x]); return parent[x]; } void Union(int u, int v) { int uOrig = u, vOrig = v; u = Find(u); v = Find(v); badComponents -= isBad[u]; badComponents -= isBad[v]; isBad[u] |= isBad[v]; if(deg[uOrig]>1 || deg[vOrig]>1) isBad[u] = true; parent[v] = u; treeSize[u] += treeSize[v]; badComponents += isBad[u]; if(isBad[u]==true) badComponentSz = treeSize[u]; } void addEdge(int u, int v) { if(Find(u)!=Find(v)) { Union(u, v); } else { if(isBad[Find(u)]==false) { isBad[Find(u)] = true; badComponents++; badComponentSz = treeSize[Find(u)]; } } deg[u]++; deg[v]++; } }; int n; DSU T; int maxDeg = 0; vector <int> adj[MAXN]; vector <pair <int, int>> allEdges; Graph(){} Graph(int n) { this->n = n; T = DSU(n); } void addEdge(int u, int v) { T.addEdge(u, v); adj[u].push_back(v); adj[v].push_back(u); allEdges.push_back({u, v}); maxDeg = max(maxDeg, int(adj[u].size())); maxDeg = max(maxDeg, int(adj[v].size())); } }; Graph G; map <int, Graph> excludedNode; void Init(int N) { G = Graph(N); for(int x = 0;x<N;x++) excludedNode[x] = Graph(N); } void initFirst() { int node = -1; for(int x = 0;x<G.n;x++) { if(G.adj[x].size()==3) { node = x; break; } } excludedNode[node] = Graph(G.n); for(int x: G.adj[node]) excludedNode[x] = Graph(G.n); for(auto it = excludedNode.begin();it!=excludedNode.end();it++) { int x = it->first; Graph &g = it->second; for(pair <int, int> e: G.allEdges) { if(e.first!=x && e.second!=x) { g.addEdge(e.first, e.second); } } } } void Link(int A, int B) { G.addEdge(A, B); /* if(G.maxDeg>=3 && excludedNode.empty()==true) { initFirst(); } else { for(auto it = excludedNode.begin();it!=excludedNode.end();it++) { int x = it->first; Graph &g = it->second; if(A!=x && B!=x) { g.addEdge(A, B); } } }*/ for(auto it = excludedNode.begin();it!=excludedNode.end();it++) { int x = it->first; Graph &g = it->second; if(A!=x && B!=x) { g.addEdge(A, B); } } } int CountCritical() { if(G.maxDeg<=2) { if(G.T.badComponents>1) return 0; if(G.T.badComponents==1) return G.T.badComponentSz; return G.n; } if(G.maxDeg>3) { return 0; } int ans = 0; for(auto it = excludedNode.begin();it!=excludedNode.end();it++) { if(it->second.T.badComponents==0) ans++; } return ans; }
#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...