oj.uz

Submission #566926

# Submission time Handle Problem Language Result Execution time Memory
566926 2022-05-23T06:29:04 Z tqbfjotld Jail (JOI22_jail) C++14
0 / 100
 5 ms 8788 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> adjl[120005];
int vis[120005];
int cur;
int fs[120005];
int ls[120005];
vector<int> mid[120005];

int A[120005];
int B[120005];

int dfs1(int node, int st, int dest, int p){
    if (node==dest){
        ls[node] = cur;
        return 1;
    }
    if (st==node){
        fs[node] = cur;
    }
    for (auto x : adjl[node]){
        if (p==x) continue;
        int res = dfs1(x,st,dest,node);
        if (res==1&&st!=node){
            mid[node].push_back(cur);
        }
        if (res==1) return 1;
    }
    return 0;
}

vector<int> adjl2[120005];

bool checkcycle(int node){
    if (vis[node]==2) return false;
    vis[node] = 1;
    for (auto x : adjl2[node]){
        if (vis[x]==1) return true;
        if (checkcycle(x)) return true;
    }
    vis[node] = 2;
    return false;
}

int main(){
    int Q;
    scanf("%d",&Q);
    while (Q--){
        int n;
        scanf("%d",&n);
        for (int x = 1; x<=n; x++){
            adjl[x].clear();
        }
        for (int x = 0; x<n-1; x++){
            int a,b;
            scanf("%d%d",&a,&b);
            adjl[a].push_back(b);
            adjl[b].push_back(a);
        }
        int m;
        scanf("%d",&m);
        for (int x = 0; x<m; x++){
            scanf("%d%d",&A[x],&B[x]);
        }
        for (int x = 1; x<=n; x++){
            fs[x] = -1;
            ls[x] = -1;
            mid[x].clear();
        }
        for (cur = 0; cur<m; cur++){
            dfs1(A[cur],A[cur],B[cur],-1);
        }
        for (int x = 0; x<m; x++){
            adjl2[x].clear();
            vis[x] = 0;
        }
        for (int x = 1; x<=n; x++){
            if (fs[x]!=-1){
                for (auto y : mid[x]){
                    adjl2[fs[x]].push_back(y);
                }
            }
            if (ls[x]!=-1){
                for (auto y : mid[x]){
                    adjl2[y].push_back(ls[x]);
                }
            }
        }
        bool ans = true;
        for (int x = 0; x<m; x++){
            if (checkcycle(x)){
                ans = false;
            }
        }
        printf(ans?"YES\n":"NO\n");
    }
}

Compilation message

jail.cpp: In function 'int main()':
jail.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
jail.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
jail.cpp:57:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~
jail.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d",&m);
      |         ~~~~~^~~~~~~~~
jail.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             scanf("%d%d",&A[x],&B[x]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8788 KB Output isn't correct
2 Halted 0 ms 0 KB -