QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #306961 | #8055. Balance | installb | RE | 0ms | 77428kb | C++14 | 6.9kb | 2024-01-17 18:40:23 | 2024-01-17 18:40:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define M 400005
struct EDGE{
int to,nx;
}Edge[M<<1];
int tt,h[M],K,B[M];
void link(int a,int b){
Edge[++tt].to=b;
Edge[tt].nx=h[a];
h[a]=tt;
}
int n,m;
using ll = long long;
using pii = pair<int,int>;
int dfn[M],dfc,low[M],col[M],cco,bri[M],A[M],siz[M];
void tarjan(int u,int fe){
dfn[u] = low[u] = ++dfc;
for(int i=h[u];i;i=Edge[i].nx){
int v = Edge[i].to;
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])bri[i]=bri[i^1]=1;
}else if(i!=(fe^1))low[u]=min(low[u],dfn[v]);
}
}
void dfs_dcc(int u,int id){
col[u] = id;
for(int i=h[u];i;i=Edge[i].nx){
int v = Edge[i].to;
if(bri[i] || col[v])continue;
dfs_dcc(v,id);
}
}
vector<int>edge[M];
vector<int>belong[M];
void Work(){
for(int i=1;i<=n;i++){
edge[i].clear();
dfn[i]=low[i]=col[i]=siz[i]=0;
}
for(int i=1;i<=2*m+1;i++)bri[i]=0;
dfc = cco = 0;
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
cco = 0;
for(int i=1;i<=n;i++){
if(col[i])continue;
cco++;
dfs_dcc(i,cco);
}
for(int i=1;i<=n;i++)siz[col[i]]++,belong[col[i]].push_back(i);
set<pii> S;
for(int now=1;now<=n;now++)
for(int i=h[now];i;i=Edge[i].nx){
int to = Edge[i].to;
if(col[to]!=col[now] && !S.count(pii(col[to],col[now]))){
edge[col[to]].push_back(col[now]);
edge[col[now]].push_back(col[to]);
S.insert(pii(col[to],col[now]));
S.insert(pii(col[now],col[to]));
}
}
}
int sz_val[M],Fr[M],Be[M],sz_T[M],sum_val[M];
int Ans_a,Ans_b,Ans_c,Ans_d,Sp;
int Lx[M],Rx[M],Index,ln[M];
int f[M][2],f_pre[M][2];
int par[M];
vector<int>Frv[M],Bev[M];
void Merge(int a,int b){
if(sz_T[b]>sz_T[a]){
Frv[a].swap(Frv[b]);
Bev[a].swap(Bev[b]);
}
if(K>2){
for(int i=0;i<Frv[b].size();i++){
Frv[a].push_back(0);
if(Frv[b][i]){//(i+1)
if(K-i-3 >= 0 && K-i-3<Bev[a].size() && Bev[a][K-(i+3)]){
Ans_a=Frv[b][i],Ans_b=Bev[a][K-i-3],Sp=i+1;
}
}
}
for(int i=0;i<Bev[b].size();i++){
Bev[a].push_back(0);
if(Bev[b][i]){
if(K-i-3 >= 0 && K-i-3<Frv[a].size() && Frv[a][K-(i+3)]){
Ans_a=Bev[b][i],Ans_b=Frv[a][K-i-3],Sp=K-i-2;
}
}
}
}
// cout<<Frv[a].size()<<' '<<Frv[b].size()<<' '<<sz_T[a]<<' '<<sz_T[b]<<endl;
for(int i=0;i<Frv[b].size();i++){
if(Frv[b][i])Frv[a][i] = Frv[b][i];
}
for(int i=0;i<Bev[b].size();i++){
if(Bev[b][i])Bev[a][i] = Bev[b][i];
}
}
void dfs(int F,int now){
par[now]=F;
ln[Lx[now]=++Index]=now;
f[now][0]=0,f[now][1]=K+1;
sz_T[now]=0;
for(int &to:edge[now])if(to!=F){
dfs(now,to);
if(f[to][0]>f[now][0]){
f[now][0]=f[to][0];
f_pre[now][0] = f_pre[to][0];
}
if(f[to][1]<f[now][1]){
f[now][1]=f[to][1];
f_pre[now][1] = f_pre[to][1];
}
Merge(now,to);
sz_T[now] += sz_T[to];
}
sz_T[now] += siz[now];
Frv[now].push_back(0);
Bev[now].push_back(0);
if(f[now][0] == Fr[sz_T[now]]-1 && sz_T[now] == sum_val[Fr[sz_T[now]]]){
f[now][0]++;
f_pre[now][0]=now;
if(f[now][0] == K-1)Ans_c = now;
Frv[now][f[now][0]-1]=now;
}
if(f[now][1] == Be[sz_T[now]]+1 && sz_T[now] == n-sum_val[Be[sz_T[now]]-1]){
f[now][1]--;
f_pre[now][1]=now;
if(f[now][1] == 2)Ans_d = now;
// cout<<Bev[now].size()<<' '<<K-f[now][1]<<endl;
Bev[now][K-f[now][1]]=now;
}
Rx[now]=Index;
}
int Ans[M];
void get_ans(int now,int v,int flg,int d){//-1 for 1 and 1 for 0
if(v==K && d==1 || v==1 && d==-1){
for(int i=Lx[now];i<=Rx[now];i++)
for(int &x:belong[ln[i]])Ans[x]=v;
return;
}
int nex = -1;
for(int &to:edge[now])if(to!=par[now]){
if(f[to][flg] == f[now][flg]+d)
nex = f_pre[to][flg];
}
assert(nex != -1);
// cout<<"OK"<<' '<<v<<' '<<now<<' '<<nex<<endl;
for(int i=Lx[now];i<Lx[nex];i++)
for(int &x:belong[ln[i]])Ans[x]=v;
for(int i=Rx[nex]+1;i<=Rx[now];i++)
for(int &x:belong[ln[i]])Ans[x]=v;
get_ans(nex,v+d,flg,d);
}
int mark[M],pos[M];
void Reset(){
memset(h+1,0,n<<2);
tt=1;
Sp=0;
K=0;
for(int i=1;i<=n;i++){
mark[i]=pos[i]=0;
sz_val[i]=Fr[i]=Be[i]=sz_T[i]=sum_val[i]=0;
Lx[i]=Rx[i]=ln[i]=0;
Frv[i].clear();
Bev[i].clear();
belong[i].clear();
edge[i].clear();
siz[i]=sz_val[i]=0;
f[i][0]=f[i][1]=f_pre[i][0]=f_pre[i][1]=0;
par[i]=0;
Ans[i]=0;
}
Index=0;
}
int main(){
int Cas=100;
cin>>Cas;
for(int _=1;_<=Cas;_++){
scanf("%d%d",&n,&m);
Reset();
for(int i=1,a,b;i<=m;i++){
scanf("%d%d",&a,&b);
link(a,b),link(b,a);
}
Work();
for(int i=1;i<=n;i++)mark[i]=0;
for(int i=1;i<=n;i++){
scanf("%d",&A[i]),mark[A[i]]=1;
}
K = 0;
for(int i=1;i<=n;i++)
if(mark[i])B[pos[i]=++K]=i;
if(K==1){
puts("Yes");
for(int i=1;i<=n;i++)printf("%d ",A[1]);
puts("");
continue;
}
for(int i=1;i<=n;i++){
A[i]=pos[A[i]];
sz_val[A[i]]++;
}
for(int i=1;i<=K;i++)sum_val[i] = sz_val[i] + sum_val[i-1];
for(int i=1,s=0;i<=K;i++){
for(int j=s+1;j<=s+sz_val[i];j++)Fr[j] = i;
s+=sz_val[i];
}
for(int i=K,s=0;i>=1;i--){
for(int j=s+1;j<=s+sz_val[i];j++)Be[j] = i;
s+=sz_val[i];
}
Ans_a=Ans_b=Ans_c=Ans_d=0;
dfs(0,1);
if(K>2 && Ans_a){
puts("Yes");
get_ans(Ans_a,Sp,0,-1);
get_ans(Ans_b,Sp+2,1,1);
for(int i=1;i<=n;i++)
if(Ans[i])printf("%d ",B[Ans[i]]);
else printf("%d ",B[Sp+1]);
puts("");
}else if(Ans_c){
puts("Yes");
get_ans(Ans_c,K-1,0,-1);
for(int i=1;i<=n;i++)
if(Ans[i])printf("%d ",B[Ans[i]]);
else printf("%d ",B[K]);
puts("");
}else if(Ans_d){
puts("Yes");
get_ans(Ans_d,2,1,1);
for(int i=1;i<=n;i++)
if(Ans[i])printf("%d ",B[Ans[i]]);
else printf("%d ",B[1]);
puts("");
}else puts("No");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 77428kb
input:
5 5 4 1 2 2 3 3 4 4 5 1 2 3 4 5 5 4 1 2 1 3 1 4 1 5 1 2 3 4 5 5 4 1 2 1 3 1 4 1 5 1 2 2 2 3 5 6 1 2 1 2 2 3 3 4 4 5 3 5 1 2 1 2 1 2 2 1 2 1 2 1 2
output:
Yes 5 4 3 2 1 No Yes 2 1 3 2 2 Yes 2 2 1 1 1 No
result:
ok ok (5 test cases)
Test #2:
score: -100
Runtime Error
input:
100000 4 3 4 2 1 3 2 1 2 1 3 2 5 7 2 5 5 3 2 3 5 1 4 3 2 4 4 3 1 3 1 1 2 3 2 2 1 2 3 1 1 1 4 7 3 4 1 4 2 3 4 3 4 2 3 1 4 3 2 3 3 2 4 6 2 4 3 1 1 2 1 2 2 3 4 2 1 1 3 3 4 7 3 2 4 2 1 2 3 4 3 2 2 4 3 4 2 1 1 1 5 5 3 2 1 5 4 5 4 3 2 1 1 2 2 3 2 3 5 2 3 1 3 3 1 3 1 2 1 3 2 3 2 3 2 1 2 1 1 2 1 1 2 3 2 1 1...
output:
Yes 2 2 1 3 No Yes 1 1 1 No No Yes 2 1 1 1 No No Yes 1 1 Yes 1 1 Yes 1 1 Yes 1 1 1 1 No Yes 1 1 1 1 1 Yes 1 3 1 1 1 Yes 1 1 1 Yes 2 1 Yes 1 1 1 1 1 Yes 2 1 No Yes 1 1 Yes 1 1 1 Yes 1 1 Yes 1 1 1 1 Yes 1 1 Yes 2 2 2 2 2 Yes 1 1 1 1 1 Yes 1 1 Yes 1 2 1 1 No Yes 1 1 No Yes 1 1 N...