Submission #709990

#	Time	Username	Problem	Language	Result	Execution time	Memory
709990		GrandTiger1729	Jail (JOI22_jail)	C++17	5 / 100	5035 ms	32140 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;
        vector<pair<int, int>> qry(q);
        for (int i = 0; i < q; i++){
            int u, v; cin >> u >> v;
            u--, v--;
            qry[i] = make_pair(u, v);
        }
        auto dis = [&](int u, int v){
            return dep[u] + dep[v] - 2 * dep[lca(u, v)];
        };
        bool flag = 0;
        for (int i = 0; i < q; i++){
            auto &[u, v] = qry[i];
            for (int j = i + 1; j < q; j++){
                auto &[uu, vv] = qry[j];
                if (dis(u, uu) + dis(uu, v) == dis(u, v) && dis(u, vv) + dis(vv, v) == dis(u, v))
                    flag = 1;
                if (dis(uu, u) + dis(u, vv) == dis(uu, vv) && dis(uu, v) + dis(v, vv) == dis(uu, vv))
                    flag = 1;
                if (dis(u, uu) + dis(uu, v) == dis(u, v) && dis(uu, u) + dis(u, vv) == dis(uu, vv))
                    flag = 1;
                if (dis(u, vv) + dis(vv, v) == dis(u, v) && dis(uu, v) + dis(v, vv) == dis(uu, vv))
                    flag = 1;
            }
        }
        cout << (!flag? "Yes": "No") << '\n';
        /*
        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: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23