QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#473268#1195. One-Way ConveyorshuangziruiWA 53ms34284kbC++144.3kb2024-07-11 23:57:492024-07-11 23:57:49

Judging History

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

  • [2024-07-11 23:57:49]
  • 评测
  • 测评结果:WA
  • 用时:53ms
  • 内存:34284kb
  • [2024-07-11 23:57:49]
  • 提交

answer

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int maxn=200010;
int i,j,k,n,m;
map<pii,int>isCon;
vector<int>V[maxn],vNode[maxn];

int cnt,dfn[maxn],low[maxn],vis[maxn];
int Sta[maxn],tp;
int Col[maxn],cNum;
vector<int>d[maxn];
void tarjan(int now,int fa){
    dfn[now]=low[now]=++cnt;
    Sta[++tp]=now;vis[now]=1;
    for(int x:V[now]){
        if(x==fa)continue;
        if(dfn[x]){
            if(vis[x])
                low[now]=min(low[now],low[x]);
        }else{
            tarjan(x,now);
            low[now]=min(low[now],low[x]);
        }
    }
    // cerr<<"tarjan now="<<now<<' '<<dfn[now]<<' '<<low[now]<<endl;
    if(dfn[now]==low[now]){
        ++cNum;
        while(Sta[tp]!=now){
            Col[Sta[tp]]=cNum;
            vis[Sta[tp]]=0;
            d[cNum].push_back(Sta[tp--]);
        }
        Col[Sta[tp]]=cNum;
        vis[Sta[tp]]=0;
        d[cNum].push_back(Sta[tp--]);
    }
}

int K;

int isGo[maxn],gNum,dep[maxn],Fa[maxn][21];

void dfs(int now,int fa){
    // cerr<<"dfs "<<now<<' '<<fa<<endl;
    Fa[now][0]=fa;
    dep[now]=dep[fa]+1;
    isGo[now]=gNum;
    for(int u:vNode[now]){
        if(u==fa)continue;
        dfs(u,now);
    }
}

void init(){
    for(int i=1;i<=cNum;i++)
        if(!isGo[i]){
            ++gNum;
            dfs(i,0);
        }
    for(int j=1;j<=20;j++)
        for(int i=1;i<=cNum;i++)
            Fa[i][j]=Fa[Fa[i][j-1]][j-1];
}

int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[Fa[x][i]]>=dep[y])x=Fa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)
        if(Fa[x][i]!=Fa[y][i]){
            x=Fa[x][i];
            y=Fa[y][i];
        }
    return Fa[x][0];
}

int Flag[maxn][2],sFlag[maxn][2];

void make(int x,int y){
    int X=Col[x],Y=Col[y];
    if(X==Y)return;
    // if(isGo[x]!=isGo[y]){
    //     puts("No");
    //     exit(0);
    // }
    int z=lca(X,Y);
    if(z==0){
        puts("No");
        exit(0);
    }
    // cerr<<"make "<<x<<" "<<y<<" | "<<X<<' '<<Y<<" -> "<<z<<endl;
    Flag[X][0]++;Flag[z][0]--;
    Flag[Y][1]++;Flag[z][1]--;
}

vector<pii>Ans;
map<pii,int>M;

int isWork[maxn];

void dfs2(int now,int fa){
    isWork[now]=1;
    for(int u:vNode[now]){
        if(u==fa)continue;
        dfs2(u,now);
        Flag[now][0]+=Flag[u][0];
        Flag[now][1]+=Flag[u][1];
    }
    if(Flag[now][0] && Flag[now][1]){
        puts("No");
        exit(0);
    }
    if(Flag[now][0])M[mp(now,fa)]=1,M[mp(now,fa)]=2;
    else M[mp(now,fa)]=2,M[mp(now,fa)]=1;
    // cerr<<now<<' '<<fa<<' '<<Flag[now][0]<<' '<<Flag[now][1]<<endl;
}

void maketree(){
    for(int i=1;i<=cNum;i++)
        if(!isWork[i]){
            dfs2(i,0);
        }
    for(int i=1;i<=n;i++)
        for(int j:V[i])
            if(i<j && Col[i]!=Col[j]){
                if(M[mp(Col[i],Col[j])]==2)Ans.push_back(mp(i,j));
                else Ans.push_back(mp(j,i));
            }
}

map<pii,int>Used;
int visCir[maxn],cntCir;

void dfs3(int now,int fa){
    // cerr<<"dfs3 now="<<now<<' '<<fa<<endl;
    visCir[now]=++cntCir;
    for(int x:V[now]){
        if(Col[x]==Col[now]){
            if(!Used[mp(x,now)]){
                Used[mp(x,now)]=Used[mp(now,x)]=1;
                Ans.push_back(mp(now,x));
            }
        }
        if(!visCir[x])dfs3(x,now);
    }
}

void makeCir(){
    for(int i=1;i<=n;i++)
        if(!visCir[i])dfs3(i,0);
}

void getAns(){
    maketree();makeCir();
    puts("Yes");
    for(auto x:Ans)
        printf("%d %d\n",x.first,x.second);
}

int main(){
    cin>>n>>m;
    for(i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        V[x].push_back(y);
        V[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(!dfn[i])tarjan(i,0);
    for(i=1;i<=n;i++)
        for(int j:V[i]){
            if(Col[i]==Col[j])continue;
            if(isCon[mp(Col[i],Col[j])])continue;
            isCon[mp(Col[i],Col[j])]=1;
            isCon[mp(Col[j],Col[i])]=1;
            vNode[Col[i]].push_back(Col[j]);
            vNode[Col[j]].push_back(Col[i]);
        }

    init();

    cin>>K;
    for(i=1;i<=K;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        make(x,y);
    }

    getAns();

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 27832kb

input:

3 2
1 2
2 3
3
1 2
1 3
2 3

output:

Yes
1 2
2 3

result:

ok OK!

Test #2:

score: 0
Accepted
time: 0ms
memory: 27692kb

input:

3 2
1 2
2 3
3
1 2
1 3
3 2

output:

No

result:

ok OK!

Test #3:

score: 0
Accepted
time: 5ms
memory: 27444kb

input:

4 4
1 2
1 3
1 4
2 3
7
1 2
1 3
1 4
2 1
2 3
3 1
3 2

output:

Yes
1 4
1 2
2 3
3 1

result:

ok OK!

Test #4:

score: 0
Accepted
time: 12ms
memory: 26076kb

input:

9990 47670
134 2450
4227 9100
1861 9948
120 8957
1161 4767
76 1714
5207 5838
2726 8974
2489 8619
2379 4933
3675 9554
344 3215
1654 6168
5630 6614
3247 5202
4456 5373
4380 6605
2626 4064
2194 6332
2749 9719
360 5059
7967 8835
5433 6494
497 6638
5945 9063
7576 7879
3550 4107
83 2891
3107 6917
2089 689...

output:

No

result:

ok OK!

Test #5:

score: 0
Accepted
time: 17ms
memory: 24340kb

input:

3219 13421
762 2133
1106 2880
2287 2476
313 992
741 1903
811 2050
1468 2184
3031 3037
403 1855
1060 1415
1792 2804
772 2956
140 2281
808 1953
895 1731
1217 1551
1264 1885
749 1082
1564 2824
1549 1741
1966 2730
112 2825
158 2625
2128 2917
128 3032
644 3194
1634 2743
1545 1961
2402 2680
2663 2814
1040...

output:

No

result:

ok OK!

Test #6:

score: 0
Accepted
time: 8ms
memory: 25724kb

input:

8013 18891
6127 6374
3969 4617
215 2699
268 6282
167 5415
1318 6256
3994 6192
4325 7186
1785 4188
6570 7153
772 5901
9 5190
873 6509
161 7476
2960 2966
4598 7170
1157 3798
758 4508
1446 5205
445 5989
686 5479
669 4711
6254 6860
1722 7020
463 3494
5063 7309
2231 6762
1208 4304
4789 5081
3925 6248
107...

output:

No

result:

ok OK!

Test #7:

score: -100
Wrong Answer
time: 53ms
memory: 34284kb

input:

9968 46595
3655 5544
5747 9340
6020 9528
5789 9882
4609 8832
1969 5167
2610 8012
324 9387
694 3647
3667 8483
4202 4963
2643 8104
1139 9679
1407 7022
9031 9944
5183 8744
3341 3858
326 2610
414 1317
657 7942
4702 5671
2072 3200
3074 3597
26 3728
288 7757
144 9580
1374 2065
2683 8068
1341 6526
2140 257...

output:

Yes
38 3
7701 5
2528 12
21 5899
5411 28
41 1675
43 2611
8563 48
2497 53
7779 64
1279 68
4366 69
2350 78
5991 79
4587 94
1435 97
2098 124
7499 126
128 3736
3731 138
139 7091
1511 148
162 5972
165 5328
7175 190
199 1169
5212 205
4113 216
4676 225
3359 239
9275 245
3134 249
8363 250
691 263
6892 269
27...

result:

wrong answer Could not reach from 7624 to 2812