oj.uz

Submission #709953

# Submission time Handle Problem Language Result Execution time Memory
709953 2023-03-15T01:22:47 Z GrandTiger1729 Jail (JOI22_jail) C++17
0 / 100
 17 ms 596 KB 
#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;
            }
        }
        bool flag = 0;
        function<void(int)> solve = [&](int u){
            vis[u] = 1;
            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 (dep[tag[v].first] <= dep[tag[u].first])
                    tag[u].first = tag[v].first;
                if (dep[tag[v].second] <= dep[tag[u].second])
                    tag[u].second = tag[v].second;
            }
            vis[u] = 0;
        };
        solve(0);
        cout << (!flag? "Yes": "No") << '\n';
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 17 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 3 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 3 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 3 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 3 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Incorrect 10 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 17 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -