제출 #582743

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582743		elkernos	Jail (JOI22_jail)	C++17	100 / 100	977 ms	273052 KiB

jail

#include <bits/stdc++.h>
 
using namespace std;
 
struct digraph {
    vector<vector<int>> g;
    vector<int> deg;
    digraph(int n) : g(n), deg(n) {}
    void add(int a, int b)
    {
        g[a].push_back(b);
        deg[b]++;
    }
    bool query(int n)
    {
        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(deg[i] == 0) {
                q.push(i);
            }
        }
        while(!q.empty()) {
            int x = q.front();
            q.pop();
            for(int y : g[x]) {
                deg[y]--;
                if(deg[y] == 0) {
                    q.push(y);
                }
            }
        }
        if(*max_element(deg.begin(), deg.begin() + n)) {
            return 0;
        }
        return 1;
    }
};
 
const int magic = 17;
 
void test_case()
{
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<vector<int>> jump(magic, vector<int>(n + 1));
    vector<int> dep(n + 1);
    function<void(int, int)> dfs = [&](int u, int p) {
        for(int to : g[u]) {
            if(to == p) {
                continue;
            }
            jump[0][to] = u;
            dep[to] = dep[u] + 1;
            dfs(to, u);
        }
    };
    dfs(1, -1);
    for(int i = 1; i < magic; i++) {
        for(int j = 1; j <= n; j++) {
            jump[i][j] = jump[i - 1][jump[i - 1][j]];
        }
    }
    auto startIdx = [&](int i, int j) {
        return (i + 1) * n + j - 1;
    };
    auto endIdx = [&](int i, int j) {
        return (i + 18) * n + j - 1;
    };
    digraph dg(36 * n);
    for(int i = 1; i < magic; i++) {
        for(int j = 1; j <= n; j++) {
            if(dep[j] + 1 >= (1 << i)) {
                dg.add(startIdx(i, j), startIdx(i - 1, j));
                dg.add(startIdx(i, j), startIdx(i - 1, jump[i - 1][j]));
                dg.add(endIdx(i - 1, j), endIdx(i, j));
                dg.add(endIdx(i - 1, jump[i - 1][j]), endIdx(i, j));
            }
        }
    }
    auto anc = [&](int a, int len) {
        for(int i = 0; len > 0; i++) {
            if(len % 2 == 1) {
                a = jump[i][a];
            }
            len /= 2;
        }
        return a;
    };
    auto lca = [&](int a, int b) {
        if(dep[a] > dep[b]) swap(a, b);
        b = anc(b, dep[b] - dep[a]);
        if(a == b) {
            return a;
        }
        for(int i = magic - 1; i >= 0; i--) {
            if(jump[i][a] != jump[i][b]) {
                a = jump[i][a];
                b = jump[i][b];
            }
        }
        return jump[0][a];
    };
	int m;
	cin >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        dg.add(startIdx(0, a), i);
        dg.add(i, endIdx(0, b));
        int l = lca(a, b);
        auto addEdge = [&](int v, int len) {
            if(len <= 0) {
                return;
            }
            int it = __lg(len);
            int w = anc(v, len - (1 << it));
            dg.add(i, startIdx(it, v));
            dg.add(i, startIdx(it, w));
            dg.add(endIdx(it, v), i);
            dg.add(endIdx(it, w), i);
        };
        addEdge(jump[0][a], dep[a] - dep[l] - 1);
        addEdge(jump[0][b], dep[b] - dep[l] - 1);
        dg.add(endIdx(0, a), i);
        dg.add(i, startIdx(0, b));
        if(a != l) {
            dg.add(i, startIdx(0, l));
        }
        if(b != l) {
            dg.add(endIdx(0, l), i);
        }
    }
    cout << (dg.query(36 * n) ? "Yes" : "No") << "\n";
}
 
int main()
{
    cin.tie(nullptr)->sync_with_stdio(0);
    int q;
    cin >> q;
    while(q--) {
        test_case();
    }
}

• 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