Submission #709958

#	Time	Username	Problem	Language	Result	Execution time	Memory
709958		GrandTiger1729	Jail (JOI22_jail)	C++17	5 / 100	241 ms	33676 KiB

jail

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    while (t--){
        int n; cin >> n;
        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; i++){
            int u, v; cin >> u >> v;
            u--, v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<bool> vis(n);
        vector<int> dep(n);
        vector<vector<int>> up(n, vector<int>(__lg(n) + 1));
        function<void(int)> dfs = [&](int u){
            vis[u] = 1;
            for (auto &v: g[u]){
                if (vis[v]) continue;
                up[v][0] = u;
                dep[v] = dep[u] + 1;
                dfs(v);
            }
            vis[u] = 0;
        };
        dfs(0);
        for (int j = 1; j <= __lg(n); j++){
            for (int i = 0; i < n; i++){
                up[i][j] = up[up[i][j - 1]][j - 1];
            }
        }
        auto lca = [&](int u, int v){
            if (dep[u] < dep[v]) swap(u, v);
            for (int i = __lg(n); i >= 0; i--){
                if (dep[up[u][i]] >= dep[v]){
                    u = up[u][i];
                }
            }
            if (u == v) return u;
            for (int i = __lg(n); i >= 0; i--){
                if (up[u][i] != up[v][i]){
                    u = up[u][i];
                    v = up[v][i];
                }
            }
            return up[u][0];
        };
        vector<pair<int, int>> tag(n);
        for (int i = 0; i < n; i++){
            tag[i] = make_pair(i, i);
        }
        int q; cin >> q;
        while (q--){
            int u, v; cin >> u >> v;
            u--, v--;
            int l = lca(u, v);
            if (dep[l] < dep[tag[u].first]){
                tag[u].first = l;
            }
            if (dep[l] < dep[tag[v].second]){
                tag[v].second = l;
            }
        }
        // cout << endl;
        // for (int i = 0; i < n; i++){
        //     cout << tag[i].first << ' ' << tag[i].second << endl;
        // }
        // cout << endl;
        bool flag = 0;
        function<void(int)> solve = [&](int u){
            vis[u] = 1;
            pair<int, int> res{u, u};
            for (auto &v: g[u]){
                if (vis[v]) continue;
                solve(v);
                if (dep[tag[v].first] <= dep[u] && dep[tag[v].second] <= dep[u])
                    flag = 1;
                if ((tag[u].first != u && dep[tag[v].first] < dep[tag[u].first]) \
                         || (tag[u].second != u && dep[tag[v].second] < dep[tag[u].second]))
                    flag = 1;
                if (dep[tag[v].first] <= dep[res.first])
                    res.first = tag[v].first;
                if (dep[tag[v].second] <= dep[res.second])
                    res.second = tag[v].second;
            }
            if (dep[res.first] <= dep[tag[u].first])
                tag[u].first = res.first;
            if (dep[res.second] <= dep[tag[u].second])
                tag[u].second = res.second;
            vis[u] = 0;
        };
        solve(0);
        cout << (!flag? "Yes": "No") << '\n';
    }
    return 0;
}

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