#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 time |
Memory |
Grader output |
| 1 |
Runtime error |
821 ms |
1048576 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
23808 KB |
WA in grader: Invalid length of the result. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
887 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1072 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
821 ms |
1048576 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
