QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#306952#8055. Balanceinstallb#WA 104ms75748kbC++146.8kb2024-01-17 18:09:582024-01-17 18:09:58

Judging History

你现在查看的是最新测评结果

  • [2024-01-17 18:09:58]
  • 评测
  • 测评结果：WA
  • 用时：104ms
  • 内存：75748kb
查看
  • [2024-01-17 18:09:58]
  • 提交

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]=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;
                }
            }
        }
    }
    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);
        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];
        }
        Merge(now,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;
        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]-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++){
        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;
    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;
        }
        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;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 75484kb

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
Wrong Answer
time: 104ms
memory: 75748kb

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...

result:

wrong answer 2-th smallest numbers are not same (test case 43)
English 繁體中文 简体中文

服务器时间: 2024-12-03 02:32:42 | 开源项目