Submission #941651

#	Time	Username	Problem	Language	Result	Execution time	Memory
941651		alextodoran	Jail (JOI22_jail)	C++17	100 / 100	849 ms	300576 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;
const int LOG_N = 17;
const int V_MAX = M_MAX + N_MAX * LOG_N * 2;

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];

int V;
vector <int> out[V_MAX + 2];
int deg[V_MAX + 2];

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

int anc[N_MAX + 2][LOG_N];
int seg_out[N_MAX + 2][LOG_N];
int seg_in[N_MAX + 2][LOG_N];

void build () {
    for (int u = 1; u <= N; u++) {
        anc[u][0] = parent[u];
    }
    for (int k = 1; k < LOG_N; k++) {
        for (int u = 1; u <= N; u++) {
            anc[u][k] = anc[anc[u][k - 1]][k - 1];
        }
    }
    V = M;
    for (int u = 1; u <= N; u++) {
        seg_out[u][0] = ++V;
        seg_in[u][0] = ++V;
        if (finish_id[u] != 0) {
            add_edge(seg_out[u][0], finish_id[u]);
        }
        if (start_id[u] != 0) {
            add_edge(start_id[u], seg_in[u][0]);
        }
    }
    for (int k = 1; k < LOG_N; k++) {
        for (int u = 1; u <= N; u++) {
            seg_out[u][k] = ++V;
            seg_in[u][k] = ++V;
            add_edge(seg_out[u][k], seg_out[u][k - 1]);
            add_edge(seg_in[u][k - 1], seg_in[u][k]);
            if (anc[u][k - 1] != 0) {
                add_edge(seg_out[u][k], seg_out[anc[u][k - 1]][k - 1]);
                add_edge(seg_in[anc[u][k - 1]][k - 1], seg_in[u][k]);
            }
        }
    }
}

int ancestor (int u, int len) {
    for (int k = 0; k < LOG_N; k++) {
        if ((len >> k) & 1) {
            u = anc[u][k];
        }
    }
    return u;
}

int lca (int u, int v) {
    if (depth[u] > depth[v]) {
        u = ancestor(u, depth[u] - depth[v]);
    }
    if (depth[v] > depth[u]) {
        v = ancestor(v, depth[v] - depth[u]);
    }
    if (u == v) {
        return u;
    }
    for (int k = LOG_N - 1; k >= 0; k--) {
        if (anc[u][k] != anc[v][k]) {
            u = anc[u][k];
            v = anc[v][k];
        }
    }
    return parent[u];
}

void add_path (int i, int u, int v) {
    int len = depth[u] - depth[v];
    for (int k = 0; k < LOG_N; k++) {
        if ((len >> k) & 1) {
            add_edge(i, seg_out[u][k]);
            add_edge(seg_in[u][k], i);
            u = anc[u][k];
        }
    }
}

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 <= V; 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;
        }
        build();
        for (int i = 1; i <= M; i++) {
            int u = start[i], v = finish[i];
            int x = lca(u, v);
            if (u != x) {
                add_path(i, parent[u], x);
            }
            if (v != x) {
                add_path(i, parent[v], x);
            }
            if (finish_id[u] != 0) {
                add_edge(i, finish_id[u]);
            }
            if (start_id[v] != 0) {
                add_edge(start_id[v], i);
            }
            if (u != x && v != x) {
                if (finish_id[x] != 0) {
                    add_edge(i, finish_id[x]);
                }
                if (start_id[x] != 0) {
                    add_edge(start_id[x], i);
                }
            }
        }
        queue <int> q;
        for (int u = 1; u <= V; 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 <= V; u++) {
            if (deg[u] > 0) {
                ok = false;
                break;
            }
        }
        cout << (ok == true ? "Yes" : "No") << "\n";
        clean();
    }

    return 0;
}

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