제출 #809166

#제출 시각아이디문제언어결과실행 시간메모리
809166Username4132Split the Attractions (IOI19_split)C++14
18 / 100
88 ms33864 KiB
#include "split.h" #include<iostream> #include<vector> #include<algorithm> #include<cassert> using namespace std; using ll = long long; using pii = pair<int, int>; #define forn(i, n) for(int i=0; i<(int)n; ++i) #define dforn(i, n) for(int i=n-1; i>=0; --i) #define PB push_back #define F first #define S second const int MAXN = 100010; int n, top, sito, A, B, C, tm, tin[MAXN], low[MAXN], si[MAXN]; bool vis[MAXN], done; vector<int> g[MAXN], tr[MAXN], ch; int target, obt=1, roo2; int ta2, ob2; vector<int> res[3]; bool marked[MAXN], used[MAXN]; void dfs1(int v, int p){ si[v]=1; vis[v]=true; tin[v]=tm++; int forced=1; bool atm=true; vector<int> fset, rest; for(int to:g[v]){ if(to==p) continue; if(vis[to]){ low[v]=min(low[v], tin[to]); } else{ tr[v].PB(to); dfs1(to, v); si[v]+=si[to]; atm&=(si[to]<A); low[v]=min(low[v], low[to]); if(low[to]>=tin[v]){ forced+=si[to]; fset.PB(to); } else rest.PB(to); } } if(atm && (si[v]>=A) && !done){ done = true; roo2=p; if(forced>n-A) top=-1; else{ top=v; sito=forced; for(int el:fset) ch.PB(el); while(sito<A){ ch.PB(rest.back()); sito+=si[rest.back()]; rest.pop_back(); } } } } void dfs2(int v){ if(obt<target){ used[v]=marked[v]=true; res[0].PB(v); ++obt; } for(int to:tr[v]) dfs2(to); } void dfs3(int v){ vis[v]=true; if(ob2<ta2){ ++ob2; used[v]=true; res[1].PB(v); } for(int to:g[v]) if(!vis[to] && !marked[to]) dfs3(to); } vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) { n=N; vector<pii> col = {{a, 0}, {b, 1}, {c, 2}}; sort(col.begin(), col.end()); A = col[0].F, B = col[1].F, C = col[2].F; forn(i, p.size()){ g[p[i]].PB(q[i]); g[q[i]].PB(p[i]); } dfs1(0, 0); if(top==-1){ vector<int> ret(n, 0); return ret; } if(sito>=B) target=B, ta2=A; else target=A, ta2=B; marked[top]=used[top]=true; res[0].PB(top); for(int el:ch) dfs2(el); assert((int)res[0].size() == target); forn(i, n) vis[i]=false; dfs3(roo2); if((int)res[0].size()==B) swap(res[0], res[1]); forn(i, n) if(!used[i]) res[2].PB(i); vector<int> ret(n); forn(i, 3) for(int el:res[i]) ret[el]=col[i].S + 1; return ret; }
#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...