Submission #553066

#	Time	Username	Problem	Language	Result	Execution time	Memory
553066		tht2005	Jail (JOI22_jail)	C++17	72 / 100	5070 ms	773872 KiB

jail

#include <bits/stdc++.h>

using namespace std;

const int N = 120005;
const int LG = 17;

int n, m, cnt, s[N], t[N], in[N], S[N], T[N], tin[N], tout[N], p[N][LG];
vector<int> aj[N], ej[N];
queue<int> q;

void dfs(int v, int p_) {
    tin[v] = ++(*tin);
    memset(p[v], 0, sizeof(p[v]));
    p[v][0] = p_;
    for(int i = 0; i + 1 < LG; ++i) {
        p[v][i + 1] = p[p[v][i]][i];
    }
    for(int u : aj[v]) {
        if(u == p_) continue;
        dfs(u, v);
    }
    tout[v] = *tin;
}

bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}
int lca(int v, int u) {
    if(anc(v, u)) return v;
    if(anc(u, v)) return u;
    for(int i = LG; i--; ) {
        if(p[v][i] && !anc(p[v][i], u)) {
            v = p[v][i];
        }
    }
    return p[v][0];
}

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);
        }
        *tin = 0;
        dfs(1, 0);
        scanf("%d", &m);
        for(int i = 1; i <= m; ++i) {
            scanf("%d %d", s + i, t + i);
            S[s[i]] = i;
            T[t[i]] = i;
        }
        for(int i = 1; i <= m; ++i) {
            int x = lca(s[i], t[i]);
            for(int v = s[i]; v != (*p[x]); v = p[v][0]) {
                if(S[v] && S[v] != i) {
                    ej[S[v]].push_back(i);
                }
                if(T[v] && T[v] != i) {
                    ej[i].push_back(T[v]);
                }
            }
            for(int v = t[i]; v != x; v = p[v][0]) {
                if(S[v] && S[v] != i) {
                    ej[S[v]].push_back(i);
                }
                if(T[v] && T[v] != i) {
                    ej[i].push_back(T[v]);
                }
            }
        }
        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] = 0;
            T[i] = 0;
            in[i] = 0;
        }
        puts((cnt == m) ? "Yes" : "No");
    }
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d", &_);
      |     ~~~~~^~~~~~~~~~
jail.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
jail.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |             scanf("%d %d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~
jail.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |             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: 11 / 11
• Subtask 7: 0 / 23