Submission #222335

#TimeUsernameProblemLanguageResultExecution timeMemory
222335LittleFlowers__Split the Attractions (IOI19_split)C++14
0 / 100
1072 ms1048580 KiB
#include <bits/stdc++.h> using namespace std; #define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;}) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l,int r){return l+rng()%(r-l+1);} #define fasty ios_base::sync_with_stdio(0),cin.tie(0); #define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a) #define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a) #define forv(a,b) for(auto&a:b) #define fi first #define se second #define pb push_back #define ii pair<int,int> #define mt make_tuple #define all(a) a.begin(),a.end() #define reset(f, x) memset(f, x, sizeof(f)) #define bit(x,i) ((x>>(i-1))&1) #define on(x,i) (x|(1ll<<(i-1))) #define off(x,i) (x&~(1<<(i-1))) #define gg exit(0); //#define unx 1 const int N=500010; int n,m,it,top,scc,a,b,c; int num[N],low[N],st[N],ed[N],dep[N],sz[N],par[N],co[N]; int f[N][22]; vector<int> ad[N],adj[N]; void tja(int u,int p=-1){ num[u]=low[u]=++it; st[++top]=u; forv(v,ad[u]) if(v!=p){ if(!num[v]){ tja(v,u); low[u]=min(low[u],low[v]); if(num[u]<=low[v]){ scc++; int x; do{ x=st[top--]; adj[scc].pb(x); adj[x].pb(scc); } while(x!=v); adj[u].pb(scc); adj[scc].pb(u); } } else low[u]=min(low[u],num[v]); } } vector<ii> val; void dfs(int u){ sz[u]=u<=n; forv(v,adj[u]) if(v!=par[u]){ par[v]=u; dfs(v); sz[u]+=sz[v]; } val.pb({sz[u],u}); } int lf,cur; void dfs1(int u,int p){ if(lf && u<=n){ co[u]=cur; lf--; } forv(v,adj[u]){ if(v==p) continue; dfs1(v,u); } } int truecol[4]; #ifndef unx vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q){ n=scc=n, m=p.size(); forinc(i,1,m){ int u=p[i-1]+1, v=q[i-1]+1; ad[u].pb(v); ad[v].pb(u); } tja(1); dfs(1); forinc(i,1,3) truecol[i]=i; if(a>b) swap(a,b),swap(truecol[1],truecol[2]); if(b>c) swap(b,c),swap(truecol[2],truecol[3]); if(a>b) swap(a,b),swap(truecol[1],truecol[2]); vector<int> ans; forinc(i,1,scc){ if(sz[i]>=a && n-sz[i]>=b){ lf=a; cur=truecol[1]; dfs1(i,par[i]); lf=b; cur=truecol[2]; dfs1(par[i],i); forinc(i,1,n) ans.push_back(co[i] ? co[i] : truecol[3]); return ans; } if(sz[i]>=b && n-sz[i]>=a){ lf=b; cur=truecol[2]; dfs1(i,par[i]); lf=a; cur=truecol[1]; dfs1(par[i],i); forinc(i,1,n) ans.push_back(co[i] ? co[i] : truecol[3]); return ans; } } forinc(i,1,n) ans.push_back(0); return ans; } #endif // unx #ifdef unx main(){ #define task "split" freopen(task".inp","r",stdin); //freopen(task".out","w",stdout); n=scc=in,m=in; a=in,b=in,c=in; forinc(i,1,m){ int u=in+1,v=in+1; ad[u].pb(v); ad[v].pb(u); } tja(1); dfs(1); forinc(i,1,3) truecol[i]=i; if(a>b) swap(a,b),swap(truecol[1],truecol[2]); if(b>c) swap(b,c),swap(truecol[2],truecol[3]); if(a>b) swap(a,b),swap(truecol[1],truecol[2]); forinc(i,1,scc){ if(sz[i]>=a && n-sz[i]>=b){ lf=a; cur=truecol[1]; dfs1(i,par[i]); lf=b; cur=truecol[2]; dfs1(par[i],i); forinc(i,1,n) cout<<(co[i] ? co[i] : truecol[3])<<" "; gg } if(sz[i]>=b && n-sz[i]>=a){ lf=b; cur=truecol[2]; dfs1(i,par[i]); lf=a; cur=truecol[1]; dfs1(par[i],i); forinc(i,1,n) cout<<(co[i] ? co[i] : truecol[3])<<" "; gg } } forinc(i,1,n) cout<<"0 "; } #endif // unx
#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...