Submission #54183

#TimeUsernameProblemLanguageResultExecution timeMemory
54183radoslav11Simurgh (IOI17_simurgh)C++14
0 / 100
8 ms6520 KiB
#include <bits/stdc++.h> #include "simurgh.h" //#include "Lgrader.cpp" using namespace std; template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } const int MAXN = (1 << 9); const int MAXM = (1 << 18); struct dsu { int par[MAXN], sz[MAXN]; void init(int n) { for(int i = 0; i <= n; i++) par[i] = i, sz[i] = 1; } int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); } bool connected(int x, int y) { return root(x) == root(y); } void unite(int u, int v) { u = root(u); v = root(v); if(u == v) return; if(sz[u] < sz[v]) swap(u, v); par[v] = u; sz[u] += sz[v]; } } d; int m, n; pair<int, int> ed[MAXM]; vector<pair<int, int> > adj[MAXN]; int dfs_time, low[MAXN], disc[MAXN]; int low_edge[MAXN], ver[MAXN]; int E[MAXN]; int par[MAXN], pe[MAXN]; vector<int> li[MAXM]; vector<int> le, Tr; bool cmp(int i, int j) { return min(low[ed[i].first], low[ed[i].second]) < min(low[ed[j].first], low[ed[j].second]); } void tarjan(int u, int pr) { low[u] = disc[u] = ++dfs_time; ver[dfs_time] = u; low_edge[u] = -1; for(auto e: adj[u]) if(e.first != pr) { int v = e.first; if(!disc[v]) { par[v] = u; pe[v] = e.second; tarjan(v, u); if(chkmin(low[u], low[v])) low_edge[u] = low_edge[v]; if(disc[u] < low[v]) E[e.second] = 1; } else if(chkmin(low[u], disc[v])) low_edge[u] = e.second; } if(low_edge[u] != -1) le.push_back(low_edge[u]); if(u != pr) Tr.push_back(pe[u]); } int R[MAXM]; int initial; int diff(int rem, int add) { vector<int> tmp; for(int e: Tr) if(e == rem) tmp.push_back(add); else tmp.push_back(e); return count_common_roads(tmp) - initial; } int cnt_good(vector<int> L) { d.init(::n); vector<int> tmp = L; for(int i: L) d.unite(ed[i].first, ed[i].second); int to_rem = 0; for(int i: Tr) if(!d.connected(ed[i].first, ed[i].second)) to_rem += E[i], d.unite(ed[i].first, ed[i].second), tmp.push_back(i); return count_common_roads(tmp) - to_rem; } void rec(vector<int> &l, int sum) { if(sum == 0) return; if(l.size() == 1) { E[l.back()] = 1; return; } vector<int> m1, m2; for(int i = 0; i < (int)l.size() / 2; i++) m1.push_back(l[i]); for(int i = l.size() / 2; i < (int)l.size(); i++) m2.push_back(l[i]); int c1 = cnt_good(m1), c2 = sum - c1; rec(m1, c1); rec(m2, c2); } std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { ::n = n; ::m = u.size(); for(int i = 0; i < ::m; i++) { ed[i] = {u[i], v[i]}; adj[u[i]].push_back({v[i], i}); adj[v[i]].push_back({u[i], i}); E[i] = -1; } tarjan(0, 0); sort(le.begin(), le.end()); le.erase(unique(le.begin(), le.end()), le.end()); sort(le.begin(), le.end(), cmp); initial = count_common_roads(Tr); for(int i: le) { int from = ed[i].first, to = ed[i].second; if(disc[from] > disc[to]) swap(from, to); while(to != from) { li[i].push_back(pe[to]); to = par[to]; } int has = -1; for(int e: li[i]) if(E[e] != -1) has = e; if(has != -1) { int df = diff(has, i); if(df == 0) E[i] = E[has]; else E[i] = E[has] ^ 1; for(int e: li[i]) if(E[e] == -1) { int df = diff(e, i); if(df == 0) E[e] = E[i]; else E[e] = E[i] ^ 1; } } else { bool fl = 0; for(int e: li[i]) { R[e] = diff(e, i); if(R[e]) fl = 1; } if(!fl) { E[i] = 0; for(int e: li[i]) E[e] = 0; } else { for(int e: li[i]) if(R[e]) { if(R[e] == 1) E[i] = 1; else E[i] = 0; break; } for(int e: li[i]) if(E[e] == -1) { int df = R[e]; if(df == 0) E[e] = E[i]; else E[e] = E[i] ^ 1; } } } } return vector<int>(); for(int i = 0; i < n; i++) { int cnt = 0; vector<int> candidates; for(auto e: adj[i]) if(E[e.second] == -1) candidates.push_back(e.second); cnt = cnt_good(candidates); rec(candidates, cnt); } vector<int> result; for(int i = 0; i < ::m; i++) if(E[i] == 1) result.push_back(i); return result; }
#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...