Submission #553021

#	Time	Username	Problem	Language	Result	Execution time	Memory
553021		tht2005	Jail (JOI22_jail)	C++17	61 / 100	5022 ms	33124 KiB

jail

#include <bits/stdc++.h>

using namespace std;

const int N = 120005;
int n, m, cnt, s[N], t[N], in[N];
vector<int> aj[N], ej[N], S[N], T[N];
queue<int> q;

bool dfs(int v, int p_, int t, int i) {
    bool ok = (v == t);
    for(int u : aj[v]) {
        if(ok) break;
        if(u == p_) continue;
        ok |= dfs(u, v, t, i);
    }
    if(ok) {
        for(int j : S[v]) {
            if(i != j) {
                ej[j].push_back(i);
            }
        }
        for(int j : T[v]) {
            if(i != j) {
                ej[i].push_back(j);
            }
        }
    }
    return ok;
}

int main() {
    int _;
    scanf("%d", &_);
    while(_--) {
        scanf("%d", &n);
        for(int i = 1; i < n; ++i) {
            int u, v;
            scanf("%d %d", &u, &v);
            aj[u].push_back(v);
            aj[v].push_back(u);
        }
        scanf("%d", &m);
        for(int i = 1; i <= m; ++i) {
            scanf("%d %d", s + i, t + i);
            S[s[i]].push_back(i);
            T[t[i]].push_back(i);
        }
        for(int i = 1; i <= m; ++i) {
            dfs(s[i], -1, t[i], i);
        }
        for(int i = 1; i <= m; ++i) {
            for(int j : ej[i]) {
                ++in[j];
            }
        }
        for(int i = 1; i <= m; ++i) {
            if(in[i] == 0) {
                q.push(i);
            }
        }
        cnt = 0;
        while(!q.empty()) {
            int v = q.front();
            q.pop();
            ++cnt;
            for(int u : ej[v]) {
                if((--in[u]) == 0) {
                    q.push(u);
                }
            }
        }
        for(int i = 1; i <= n; ++i) {
            aj[i].clear();
            ej[i].clear();
            S[i].clear();
            T[i].clear();
            in[i] = 0;
        }
        puts((cnt == m) ? "Yes" : "No");
    }
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d", &_);
      |     ~~~~~^~~~~~~~~~
jail.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
jail.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |             scanf("%d %d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~
jail.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |             scanf("%d %d", s + i, t + i);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23