Submission #941617

#	Time	Username	Problem	Language	Result	Execution time	Memory
941617		alextodoran	Jail (JOI22_jail)	C++17	72 / 100	5056 ms	978100 KiB

jail

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 120000;
const int M_MAX = N_MAX;

int Q;

int N;
vector <int> adj[N_MAX + 2];
int M;
int start[M_MAX + 2], finish[M_MAX + 2];

int parent[N_MAX + 2];
int depth[N_MAX + 2];

void dfs (int u) {
    for (int v : adj[u]) {
        if (v != parent[u]) {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            dfs(v);
        }
    }
}

int start_id[N_MAX + 2], finish_id[N_MAX + 2];

vector <int> out[M_MAX + 2];
int deg[M_MAX + 2];

void add_edge (int u, int v) {
    out[u].push_back(v);
    deg[v]++;
}

void on_path (int i, int u) {
    if (start_id[u] != 0 && start_id[u] != i) {
        add_edge(start_id[u], i);
    }
    if (finish_id[u] != 0 && finish_id[u] != i) {
        add_edge(i, finish_id[u]);
    }
}

void clean () {
    for (int u = 1; u <= N; u++) {
        adj[u].clear();
        parent[u] = 0;
        depth[u] = 0;
        start_id[u] = 0;
        finish_id[u] = 0;
    }
    for (int u = 1; u <= M; u++) {
        out[u].clear();
        deg[u] = 0;
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> Q;
    while (Q--) {
        cin >> N;
        for (int i = 1; i <= N - 1; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dfs(1);
        cin >> M;
        for (int i = 1; i <= M; i++) {
            cin >> start[i] >> finish[i];
            start_id[start[i]] = i;
            finish_id[finish[i]] = i;
        }
        for (int i = 1; i <= M; i++) {
            int u = start[i], v = finish[i];
            while (u != v) {
                if (depth[u] > depth[v]) {
                    on_path(i, u);
                    u = parent[u];
                } else {
                    on_path(i, v);
                    v = parent[v];
                }
            }
            on_path(i, u);
        }
        queue <int> q;
        for (int u = 1; u <= M; u++) {
            if (deg[u] == 0) {
                q.push(u);
            }
        }
        while (q.empty() == false) {
            int u = q.front();
            q.pop();
            for (int v : out[u]) {
                if (--deg[v] == 0) {
                    q.push(v);
                }
            }
        }
        bool ok = true;
        for (int u = 1; u <= M; u++) {
            if (deg[u] > 0) {
                ok = false;
                break;
            }
        }
        cout << (ok == true ? "Yes" : "No") << "\n";
        clean();
    }

    return 0;
}

• 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