Submission #1111304

#TimeUsernameProblemLanguageResultExecution timeMemory
1111304lmToT27Parachute rings (IOI12_rings)C++17
52 / 100
4067 ms49880 KiB
#include <bits/stdc++.h> #define all(dataStructure) dataStructure.begin(),dataStructure.end() typedef long long ll; using namespace std; namespace std { template <typename T, int D> struct _vector : public vector <_vector <T, D - 1>> { static_assert(D >= 1, "Dimension must be positive!"); template <typename... Args> _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {} }; // _vector <int, 3> a(n, m, k);: int a[n][m][k]. // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x. template <typename T> struct _vector <T, 1> : public vector <T> { _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {} }; } const int MAX = 1e6 + 3; const ll MOD[] = {1000000007, 998244353}; int n, q; pair <int, int> eg[MAX]; int m; struct graph_t { // graph G after deleting vertex "deleted" int valid; // checking whether graph G is perfect or not int deleted; // vertex we deleted from the graph int deg[MAX], pa[MAX]; int findpa(int u) { return u == pa[u] ? u : pa[u] = findpa(pa[u]); } void join(int u, int v) { deg[u]++; deg[v]++; u = findpa(u); v = findpa(v); pa[v] = u; } void addEg(int u, int v) { if (!valid || u == deleted || v == deleted) return; if (deg[u] == 2 || deg[v] == 2 || findpa(u) == findpa(v)) return void(valid = 0); // graph must not contain cycle or with deg >= 3 join(u, v); } graph_t(int chosen) { valid = 1; deleted = chosen; for (int i = 0; i < n; i++) pa[i] = i, deg[i] = 0; for (int i = 0; i < m; i++) addEg(eg[i].first, eg[i].second); } }; vector <graph_t> subGraphs; int pa[MAX], sz[MAX]; bool badGraph; // no solulu for this graph int adj[MAX][3], deg[MAX]; int circleSize; int findpa(int u) { return u == pa[u] ? u : pa[u] = findpa(pa[u]); } bool join(int u, int v) { u = findpa(u); v = findpa(v); if (u != v) { pa[v] = u; sz[u] += sz[v]; return 1; } return 0; } void Init(int _n) { n = _n; for (int i = 0; i < n; i++) pa[i] = i, sz[i] = 1; } void Link(int u, int v) { if (badGraph) return; if (subGraphs.size()) { for (int i = 0; i < (int)subGraphs.size(); i++) subGraphs[i].addEg(u, v); } else { eg[m++] = make_pair(u, v); adj[u][deg[u]++] = v; adj[v][deg[v]++] = u; if (deg[u] < deg[v]) swap(u, v); if (deg[u] == 3) { subGraphs.push_back(graph_t(u)); for (int i = 0; i < 3; ++i) { subGraphs.push_back(graph_t(adj[u][i])); } return; } if (!join(u, v)) { if (circleSize != 0) badGraph = 1; else circleSize = sz[findpa(u)]; } } } int CountCritical() { if (badGraph) return 0; if (subGraphs.size()) { int res = 0; for (int i = 0; i < (int)subGraphs.size(); i++) res += subGraphs[i].valid; return res; } if (circleSize) return circleSize; 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...