Submission #306371

#TimeUsernameProblemLanguageResultExecution timeMemory
306371AngelKnowsSplit the Attractions (IOI19_split)C++14
29 / 100
2037 ms11380 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define fi first #define se second #define pi pair<int,int> #define mp make_pair #define sz(x) ((int)(x).size()) typedef long long ll; const int inf=0x3f3f3f3f; const ll linf=1e18; const int N=100000+10; const int M=200000+10; const double eps=1e-5; const int mo=1e9+7; int n,m,A,B,C,a,b,c; int head[N]; int nxt[2*M]; int to[2*M]; int cnt; int dfn[N],nn; int f[N]; int num[N]; int sz[N]; bool colored[N]; bool found=0; bool vis[N]; int remain; int colors[4]; int ans[N]; bool taken[N]; void color(int x,int fa) { colored[x]=1; int y; for (int i=head[x];i;i=nxt[i]) { y=to[i]; if (y!=fa&&dfn[y]>dfn[x]) { color(y,x); } } } void add(int x,int y) { nxt[++cnt]=head[x]; to[cnt]=y; head[x]=cnt; nxt[++cnt]=head[y]; to[cnt]=x; head[y]=cnt; } void dfs(int x,int fa) { int y; sz[x]=1; dfn[x]=++nn; f[x]=nn; for (int i=head[x];i;i=nxt[i]) { y=to[i]; if (y!=fa) { if (!dfn[y]) { dfs(y,x); sz[x]+=sz[y]; num[x]++; f[x]=min(f[x],f[y]); } else f[x]=min(f[x],dfn[y]); } } } void solve(int x,int fa) { int y; int p=0,cntb=0,sum=0; for (int i=head[x];i;i=nxt[i]) { y=to[i]; if (y!=fa&&dfn[y]>dfn[x]) { if (sz[y]>=b) { p=y; cntb++; } } } if (cntb>=2) { color(p,x); found=1; return; } else if (cntb==1) { if (n-sz[p]>=c) { color(p,x); found=1; return; } else { solve(p,x); } } else { sum=n-sz[x]; for (int i=head[x];i;i=nxt[i]) { y=to[i]; if (y!=fa&&dfn[y]>dfn[x]) { if (f[y]<dfn[x]) { // 有前向边连接上树 sum+=sz[y]; taken[y]=1; if (sum>=c) { // find // 注意find处理完后要退出循环 for (int j=head[x];j;j=nxt[j]) { y=to[j]; if (y!=fa&&dfn[y]>dfn[x]) { if (!taken[y]) { color(y,x); } } } colored[x]=1; found=1; return; } } } } for (int i=head[x];i;i=nxt[i]) { y=to[i]; if (y!=fa&&dfn[y]>dfn[x]) { if (f[y]>=dfn[x]&&sz[y]>=c) { // find color(y,x); found=1; return; } } } for (int i=head[x];i;i=nxt[i]) { y=to[i]; if (y!=fa&&dfn[y]>dfn[x]) { if (f[y]<dfn[x]&&sz[y]>=c) { // find color(y,x); found=1; return; } } } // 无解 } } void grow(int x) { if (remain==0) { return; } vis[x]=1; remain--; if (remain==0) { return; } int y; for (int i=head[x];i;i=nxt[i]) { y=to[i]; if (!vis[y]&&colored[y]==colored[x]) { grow(y); } } } vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) { n=N,m=int(P.size()),a=A,b=B,c=C; REP(i,0,2) colors[i]=i+1; a=A,b=B,c=C; vector<int> res; if (c>a) { swap(c,a); swap(colors[2],colors[0]); } if (c>b){ swap(c,b); swap(colors[2],colors[1]); } if (b>a) { swap(a,b); swap(colors[0],colors[1]); } for (int i=0;i<m;i++) add(P[i]+1,Q[i]+1); int maxsz=0,p=0,root=1; dfs(root,0); int y; for (int i=head[root];i;i=nxt[i]) { y=to[i]; //if (y!=fa) { // 树根没有fa if (maxsz<sz[y]) { maxsz=sz[y]; p=y; } //} } if (c<=maxsz&&maxsz<=a) { color(p,root); found=1; } else if (maxsz<c) { // 无解 } else if (maxsz>a) { if (n-maxsz>=c) { color(p,root); found=1; } else if (n-maxsz<c) { solve(p,root); } } if (found) { int s=0; FOR(i,n) if (colored[i]) s++; if (n-s>=s) { FOR(i,n) if (colored[i]) { remain=c; grow(i); FOR(j,n) if (vis[j]) ans[j]=colors[2]; break; } FOR(i,n) if (!colored[i]) { remain=b; grow(i); FOR(j,n) { if (vis[j]&&!ans[j]) { ans[j]=colors[1]; } else if (!vis[j]) { ans[j]=colors[0]; } } break; } } else { FOR(i,n) if (colored[i]) { remain=b; grow(i); FOR(j,n) if (vis[j]) ans[j]=colors[1]; break; } FOR(i,n) if (!colored[i]) { remain=c; grow(i); FOR(j,n) { if (vis[j]&&!ans[j]) { ans[j]=colors[2]; } else if (!vis[j]) { ans[j]=colors[0]; } } break; } } FOR(i,n) res.pb(ans[i]); } else { FOR(i,n) res.pb(0); } return res; } /* int main() { int n, m, a, b, c; assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c)); vector<int> p(m), q(m); for (int i=0; i<m; i++) assert(2 == scanf("%d%d", &p[i], &q[i])); fclose(stdin); vector<int> result = find_split(n, a, b, c, p, q); for (int i=0; i<(int)result.size(); i++) printf("%s%d", ((i>0)?" ":""), result[i]); printf("\n"); fclose(stdout); return 0; }*/
#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...