QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #306940 | #8055. Balance | installb# | RE | 4ms | 59336kb | C++14 | 6.4kb | 2024-01-17 17:19:08 | 2024-01-17 17:19:09 |
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]=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 hv_ans_b[M];
int Ans_a,Ans_b,Ans_c,Ans_d;
int Lx[M],Rx[M],Index,ln[M];
int f[M][2],f_pre[M][2];
int par[M];
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] = siz[now];
for(int &to:edge[now])if(to!=F){
dfs(now,to);
sz_T[now] += sz_T[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];
}
if(hv_ans_b[to])hv_ans_b[now] = hv_ans_b[to];
}
// cout<<now<<' '<<sz_T[now]<<endl;
if(f[now][0] == Fr[sz_T[now]]-1 && sz_T[now] == sum_val[Fr[sz_T[now]]]){
// cout<<now<<endl;
f[now][0]++;
f_pre[now][0]=now;
if(f[now][0] == K-1)Ans_c = 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] == K)hv_ans_b[now] = now;
if(f[now][1] == 2)Ans_d = now;
}
Rx[now]=Index;
}
void redfs(int F,int now,int hv_ans_bb){
int fi=0,se=0;
for(int &to:edge[now])if(to!=F){
if(hv_ans_b[to]){
if(!fi)fi = hv_ans_b[to];
else se = hv_ans_b[to];
}
}
for(int &to:edge[now])if(to!=F){
int tag = hv_ans_bb;
if(!tag && fi && fi != hv_ans_b[to]) tag = fi;
if(!tag && se && se != hv_ans_b[to]) tag = se;
redfs(now,to,tag);
}
if(hv_ans_bb && f[now][0] == K-2 && sz_T[now] == sum_val[Fr[sz_T[now]]]){
Ans_a=now, Ans_b=hv_ans_bb;
}
}
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]-1)
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);
}
void Reset(){
memset(h+1,0,n<<2);
tt=1;
for(int i=1;i<=n;i++){
belong[i].clear();
edge[i].clear();
siz[i]=sz_val[i]=hv_ans_b[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=1;
cin>>Cas;
while(Cas--){
// n=100000,m=200000;
scanf("%d%d",&n,&m);
Reset();
for(int i=1,a,b;i<=m;i++){
// a=rand()%n+1,b=rand()%n+1;
// while(a==b)a=rand()%n+1,b=rand()%n+1;
scanf("%d%d",&a,&b);
link(a,b),link(b,a);
}
Work();
static int mark[M],pos[M];
for(int i=1;i<=n;i++)mark[i]=0;
for(int i=1;i<=n;i++)//A[i]=rand()%1000+1,mark[A[i]]=1;
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;
}
Ans_a=Ans_b=0;
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;
// cout<<f[5][0]<<endl;
dfs(0,1);
redfs(0,1,0);
if(K>2 && Ans_a){
puts("Yes");
get_ans(Ans_a,K-2,0,-1);
get_ans(Ans_b,K,1,1);
for(int i=1;i<=n;i++)
if(Ans[i])printf("%d ",B[Ans[i]]);
else printf("%d ",B[K-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;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 59336kb
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 2 2 3 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...