Submission #566926

#	Time	Username	Problem	Language	Result	Execution time	Memory
566926		tqbfjotld	Jail (JOI22_jail)	C++14	0 / 100	5 ms	8788 KiB

jail

#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 (stderr)

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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23