QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#38495#1195. One-Way ConveyorszshcccWA 197ms26420kbC++9.3kb2022-07-06 01:22:372022-07-06 01:22:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-06 01:22:38]
  • 评测
  • 测评结果:WA
  • 用时:197ms
  • 内存:26420kb
  • [2022-07-06 01:22:37]
  • 提交

answer

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define pb push_back 
#define SZ(a) ((int)(a.size()))
#define rep(i,a,b) for(int i=a;i<b;i++)
#define mp make_pair

using namespace std;
const int N=2e6+10;
const int mod=998244353;
// unordered_map<pii,int>has;  
map<pii,int>has;
// ll hhash(int u,int v){
//     return u*1e9+v;
// }
// unordered_map<pii,int>link;
struct Edge{
    int u,v,id;
};
// vector<pii> ans;
set<pii>ans;  //用set更方便!!!
Edge ed[N];
namespace Tarjan{
    int e[N<<1],ne[N<<1],h[N],idx;
    int h2[N];
    // unordered_map<int,int>has;

    int sz[N];
    void add(int a,int b){
        e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    }
    void add2(int a,int b){
        e[idx]=b,ne[idx]=h2[a],h2[a]=idx++;

    }
    int isbridge[N];
    int dfn[N],low[N],timestamp;
    // int fa[N];
    int id[N],dcc_cnt;
    int stk[N],top;
    void tarjan(int u,int from){
        dfn[u]=low[u]=++timestamp;
        stk[++top]=u;
        for(int i=h[u];~i;i=ne[i]){
            int j=e[i];
            if(!dfn[j]){
                // fa[j]=u;
                tarjan(j,i);
                low[u]=min(low[j],low[u]);

                if(low[j]>dfn[u]){
                    // 是桥
                    isbridge[i]=isbridge[i^1]=1;
                }
            }
            else if(i!=(from^1)){
                //则找到强连通分量
                low[u]=min(low[u],dfn[j]);
            }

        }
        
        // if(dfn[u]==low[u]){
        //     ++dcc_cnt;
        //     // int sz=0;
        //     int y=u;
            // do{
            //     // sz++;
            //     sz[dcc_cnt]++;   
            //     if(y!=stk[top]){
            //         // if(y==6990||stk[top]==6990)cout<<" !!!  "<<y<<" "<<stk[u]<<endl;
            //         // 栈顶不一定和u相连!!!
            //         // ans.insert(mp(y,stk[top]));//出栈一定是dfs 联通序,仍然有许多边没有记录!!!
            //         // has[mp(y,stk[top])]=1;

            //     }
            //     // cout<<y<<"   circle  "<<stk[top]<<endl;
            //     y=stk[top--];
            //     id[y]=dcc_cnt;
            // }while(y!=u);
          

        // }

    }
    int vis[N<<1];
// 确定一个连通分量内
void getiner(int u){
    id[u]=dcc_cnt;
    // cout<<u<<"  u"<<endl;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(isbridge[i])continue;
        if(!vis[i]&&!vis[i^1]){
            ans.insert(mp(u,j));
            vis[i]=vis[i^1]=1;
        }
        
        if(id[j])continue;
        getiner(j);
        

    }

}

}

using namespace Tarjan;
namespace LCA{
    int dep[N],fa[N][21];

    void init(int u,int ff){

        #ifdef deb
        cout<<"u  ff  "<<u<<"  "<<ff<<endl;
        #endif
        dep[u]=dep[ff]+1;
        fa[u][0]=ff;
        for(int i=1;i<=20;i++){
            fa[u][i]=fa[fa[u][i-1]][i-1];
        }
        for(int i=h2[u];~i;i=ne[i]){
            int j=e[i];
            if(j==ff)continue;
            init(j,u);
        }
    }
    int lca(int u,int v){
        if(dep[u]<dep[v])swap(u,v);
        for(int i=20;i>=0;i--){
            if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
        }
        if(dep[u]==dep[v])return u;
        for(int i=20;i>=0;i--){
            if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
        }
        return fa[u][0];
    }
}
int uptree[N],downtree[N];


using namespace LCA;
// 按照题解的差分方式,前缀时要先子树后自己
int dire[N];

bool dfs1(int u,int ff,int from){
    // uptree[u]=uptree[ff]+uptree[u];
    for(int i=h2[u];~i;i=ne[i]){
        int j=e[i];if(j==ff)continue;
        if(!dfs1(j,u,i))return false;
        uptree[u]+=uptree[j];
    }
    if(from==-1)return true;
    // cout<<u<<"   "<<uptree[u]<<"   "<<downtree[u]<<"   tree"<<endl;
    if(uptree[u]>0&&downtree[u]>0){  //指的是该节点上面的边 (父边)
        return false;
    }
    if(uptree[u]>0){
        // cout<<u<<"     ->  "<<ff<<"   "<<id[4]<<endl;
        has[mp(u,ff)]=1;

        // 怎么映射定向???
        // 
        // 按照给出的顺序

        // 直接记录点对比记录边的朝向更加方便!!!!
        // dire[has[from]]=0;
        // dire[has[from]^1]=1;// 同向

        //向上 
    }
    else {
        has[mp(ff,u)]=1; //判断方向时直接根据id[u],id[v]确定,不用映射

        // dire[from]=dire[from^1]=2;//向下
        // dire[has[from]]=1;dire[has[from]^1]=0;
    }
    return true;
}



// void getans(int u,int ff,int from){
//     if(ff){
//         if(uptree[u]-uptree[ff]>0){
//             dire[has[from]]=0;  //异乡
//             dire[has[from]^1]=1;   //同向
//             //代表向上
//         }
//         else {
//             dire[has[from]]=dire[has[from]^1]=2;
//         }
//     }
//     for(int i=h2[u];~i;i=ne[i]){
//         if(i==from^1)continue;
//         int j=e[i];
//         getans(j,u,i);
//     }
// }

signed main(){
    int n,m;
    // freopen("C:/Users/lenovo/Desktop/div1/day5/007.in","r",stdin);
    cin>>n>>m;
    // cout<<n<<"  "<<n<<endl;
    memset(h,-1,sizeof h);
    memset(h2,-1,sizeof h2);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        // ed[i]=mp(u,v);
        ed[i]={u,v,idx};
        
        add(u,v),add(v,u);
    }
    tarjan(1,1); 
    for(int i=1;i<=n;i++){
        
        if(!id[i]){
            ++dcc_cnt;
            getiner(i);
            // cout<<endl;
        }
    }
    
    // cout<<dcc_cnt<<endl;
    // exit(0);
    for(int i=1;i<=m;i++){
        // 给出的是uv
        int u=ed[i].u,v=ed[i].v;
        if(id[u]!=id[v]){
            // cout<<u<<"  uv "<<v<<endl;
            // has[idx]=ed[i].id;
            // has[idx+1]=ed[i].id^1;
            // 连的时候也是先u后v
            add2(id[u],id[v]),add2(id[v],id[u]);
        }
    }
   
    init(1,0);
    // for(int i=1;i<=dcc_cnt;i++){
    //     for(int j=0;j<2;j++){
    //         // cout<<fa[i][j]<<"  "<<i<<"  "<<j<<"  "<<endl;
    //     }
    //     cout<<endl;
    // }
    // cout<<lca(1,2)<<"  !!!"<<endl;
    // exit(0);
    int nn;
    vector<pii> up,down; 
    cin>>nn;
    rep(i,0,nn){
        int u,v;
        cin>>u>>v;
        u=id[u],v=id[v];
        if(u==v)continue;
        // cout<<u<<"   "<<v<<"  aft "<<endl;
        int Lca=lca(u,v);

        if(Lca!=u&&Lca!=v){
            up.pb(mp(u,Lca)),down.pb(mp(Lca,v));
        }
        else if(dep[u]>dep[v]){
            
            up.pb(mp(u,v));

        }
        else{

            /*
9 12 
1 2 
2 3
3 1
2 4
4 5
5 6
4 6
6 8
5 7
3 9
2 9
1 9
5
2 4
2 8
2 7
9 1
9 2

            */
           
            down.pb(mp(u,v));
        }
    }
    // for(auto t:down){
    //     cout<<t.fi<<"  down "<<t.se<<endl;
    // }
    // for()
    // exit(0);
    for(auto t:up){
        int be=t.fi,ed=t.se;
        uptree[be]++,uptree[ed]--;  //边的上面的点的前缀和<0则该边向上
    }
    for(auto t:down){
        int be=t.fi,ed=t.se;
        downtree[ed]++,downtree[be]--;
    }
   
    if(dfs1(1,1,-1)){
        puts("Yes"); 
        // cout<<has[mp(2,1)]<<"    "<<has[mp(1,2)]<<endl;
        // exit(0);
        for(int i=0;i<2*m;i+=2){
            int u=e[i],v=e[i^1]; 
            // if(u==6990||v==6990){
            //     cout<<u<<"  "<<v<<endl;
            //   }
            if(id[u]!=id[v]){
                if(has[mp(id[u],id[v])]){
                    // cout<<u<<"    "<<v<<endl;
                    // cout<<"   !!!!!!!!!"<<endl;
                    ans.insert(mp(u,v));
                }
                else{
                    // ans.em
                    ans.insert(mp(v,u));
                }
            }
           
            // cout<<dire[i]<<"  "<<endl<<endl;
            // if(dire[i]==1){
            //     cout<<e[i^1]<<" "<<e[i]<<endl;
            // }
            // else {
            //     cout<<e[i]<<" "<<e[i^1]<<endl;
            // }
            
        } 
        // for(int i=0;i<2*m;i+=2){
        //       int u=e[i],v=e[i^1];
             
        //     if(ans.find(mp(u,v))==ans.end()&&ans.find(mp(v,u))==ans.end()){
        //         ans.insert(mp(u,v));

        //     }
        // }
        for(auto t:ans){
                
                // cout<<t.fi<<" "<<t.se<<endl;
                cout<<t.fi<<" "<<t.se<<endl;
                // if(t.fi==100)break;

            }

    }
    else{
        puts("No");
        return 0;
    }
    // // for(auto t:down){
    // //     int be=t.fi,ed=t.se;  //从上往下
    // //     if(uptree[fa[ed][0]]-uptree[fa[be][0]]!=0){  //把边变成点才可以这样差分!!!(可以try)
    // //         puts("No");
    // //         return 0;
    // //     }
    // //     else{
    // //         uptree[be]--,uptree[ed]++;
    // //     }
    // // }

    // getans(1,0,-1);
    // puts("Yes");
    // for(int i=0;i<idx;i+=2){
    //     int a=e[i],b=e[i^1];
    //     if(dep[a]<dep[b])swap(a,b);
    //     if(dire[i]==2){
    //         cout<<a<<"  "<<b<<endl;
    //     }
    //     else {
    //         cout<<b<<"  "<<a<<endl;
    //     }
    // }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 21996kb

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: 2ms
memory: 19964kb

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: 2ms
memory: 22028kb

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 3
1 4
2 1
3 2

result:

ok OK!

Test #4:

score: 0
Accepted
time: 36ms
memory: 26420kb

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: 31ms
memory: 23928kb

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: 12ms
memory: 21964kb

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: 197ms
memory: 26364kb

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
1 8708
2 8381
3 38
3 5180
4 7850
5 5336
5 7701
6 7423
7 4226
8 3312
9 3865
10 3694
11 207
12 2528
12 5335
13 8762
14 7041
15 6207
16 7676
17 3082
18 9139
19 2628
20 896
21 5899
21 9962
22 8568
23 1565
24 7478
25 801
26 8588
27 17
27 6796
28 6698
29 5235
30 6342
31 9700
32 1742
33 1159
33 6403
34...

result:

wrong answer Could not reach from 6128 to 4061