제출 #749796

#제출 시각아이디문제언어결과실행 시간메모리
749796groguSplit the Attractions (IOI19_split)C++14
100 / 100
171 ms34164 KiB
#include "split.h" #define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #include <bits/stdc++.h> #define ld double #define ll int #define ull unsigned long long #define llinf 100000000000000000LL // 10^17 #define iinf 2000000000 // 2*10^9 #define pb push_back #define eb emplace_back #define popb pop_back #define fi first #define sc second #define endl '\n' #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define all(a) a.begin(),a.end() #define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;} #define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;} #define si(a) (ll)(a.size()) using namespace std; const ll maxn = 200005; ll n,m; vector<ll> g[maxn]; vector<ll> c[maxn]; vector<ll> e[maxn]; ll dsu[maxn],sz[maxn],tsz = 0; ll x,y,xid,yid; ll poc,col,colid; bool ok; ll sub[maxn]; ll par[maxn]; bool vis[maxn]; vector<ll> ans; void dfs(ll u,ll p){ sub[u] = 1; par[u] = p; vis[u] = 1; for(ll s : g[u]){ if(vis[s]) continue; dfs(s,u); e[u].pb(s); e[s].pb(u); sub[u]+=sub[s]; } if(sub[u]>=x&&n-sub[u]>=y){ poc = u; col = x; colid = xid; ok = 1; } if(sub[u]>=y&&n-sub[u]>=x){ poc = u; col = y; colid = yid; ok = 1; } } void dfscol(ll u,ll p,ll col,ll &z){ if(z){ ans[u] = col; z--; } for(ll s : e[u]){ if(s==p) continue; dfscol(s,u,col,z); } } ll cen(ll u,ll p){ for(ll s : e[u]){ if(s==p) continue; if(sub[s]*2>n) return cen(s,u); } return u; } void dfscomp(ll u,ll p){ dsu[u] = tsz; sz[tsz]++; for(ll s : e[u]){ if(s==p) continue; dfscomp(s,u); } } ll curcnt = 0; ll use[maxn]; void dfscheck(ll u,ll st){ vis[u] = 1; if(!ok){ curcnt+=sz[u]; use[u] = st; if(curcnt>=x) ok = 1; } for(ll s : c[u]){ if(vis[s]) continue; dfscheck(s,st); if(ok) return; } } void dfscol2(ll u,ll col,ll &z,ll st){ if(z) ans[u] = col,z--; else return; for(ll s : g[u]) if(use[dsu[s]]==st&&!ans[s]) dfscol2(s,col,z,st); } void dfscol3(ll u,ll col,ll &z){ if(z) ans[u] = col,z--; else return; for(ll s : g[u]) if(!ans[s]) dfscol3(s,col,z); } vector<int> find_split(int N, int A,int B,int C, vector<int> p, vector<int> q) { n = N; m = si(p); vector<pll> v; v.pb({A,1}); v.pb({B,2}); v.pb({C,3}); sort(all(v)); x = v[0].fi; xid = v[0].sc; y = v[1].fi; yid = v[1].sc; for(ll i = 1;i<=m;i++){ ll x = p[i-1] + 1; ll y = q[i-1] + 1; g[x].pb(y); g[y].pb(x); } dfs(1,1); ans.resize(n+1); if(ok){ ll tmp = col; dfscol(poc,par[poc],colid,col); tmp^=y; tmp^=x; dfscol(par[poc],poc,colid^xid^yid,tmp); for(ll i = 1;i<=n;i++){ if(ans[i]==0) ans[i] = v[2].sc; } reverse(all(ans)); ans.popb(); reverse(all(ans)); return ans; } ll root = cen(1,1); for(ll j : e[root]){ ++tsz; dfscomp(j,root); } for(ll i = 1;i<=n;i++){ if(i==root) continue; for(ll j : g[i]){ if(j==root) continue; c[dsu[i]].pb(dsu[j]); c[dsu[j]].pb(dsu[i]); } } fill(vis,vis+1+n,0); for(ll i = 1;i<=tsz;i++){ if(vis[i]) continue; curcnt = 0; dfscheck(i,i); if(ok){poc = i; break;} } if(!ok){ans.popb(); return ans;} for(ll i = 1;i<=n;i++){ if(dsu[i]==poc){ dfscol2(i,xid,x,poc); break; } } dfscol3(root,yid,y); for(ll i = 1;i<=n;i++){ if(ans[i]==0) ans[i] = v[2].sc; } reverse(all(ans)); ans.popb(); reverse(all(ans)); return ans; } /** 6 5 2 2 2 0 1 0 2 0 3 0 4 0 5 9 10 4 2 3 0 1 0 2 0 3 0 4 0 6 0 8 1 7 3 7 4 5 5 6 **/
#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...