Submission #1143891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143891		antonn	Jail (JOI22_jail)	C++20	72 / 100	3597 ms	1114112 KiB

jail

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 120000 + 7;
const int L = 20;

vector<int> g[N], gg[N];
int x[N], y[N];
int dep[N], par[N], anc[L][N];

void dfs(int u, int p = 0) {
    anc[0][u] = p;
    dep[u] = dep[p] + 1;
    par[u] = p;
    for (auto v : g[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int h = L - 1; h >= 0; --h) {
        if (dep[a] - (1 << h) >= dep[b]) {
            a = anc[h][a];
        }
    }
    if (a == b) return a;
    for (int h = L - 1; h >= 0; --h) {
        if (anc[h][a] != anc[h][b]) {
            a = anc[h][a];
            b = anc[h][b];
        }
    }
    return anc[0][a];
}

vector<int> ord;
int vis[N];

void dfs2(int u) {
    vis[u] = 1;
    for (auto v : gg[u]) {
        if (!vis[v]) {
            dfs2(v);
        }
    }
    ord.push_back(u);
}

void solve() {
    int n; cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int m; cin >> m;
    vector<int> has(n + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> x[i] >> y[i];
        has[y[i]] = i;
    }
    
    dfs(1);
    for (int h = 1; h < L; ++h) {
        for (int i = 1; i <= n; ++i) {
            anc[h][i] = anc[h - 1][anc[h - 1][i]];
        }
    }
    
    for (int i = 1; i <= m; ++i) {
        int z = lca(x[i], y[i]);
        int u = x[i];
        while (u != z) {
            if (has[u] > 0) {
                // cout << "! " << i << " " << has[u] << "\n";
                gg[i].push_back(has[u]);
            }
            u = par[u];
        }
        u = y[i];
        while (u != z) {
            if (has[u] > 0) {
                // cout << "! " << i << " " << has[u] << "\n";
                gg[i].push_back(has[u]);
            }
            u = par[u];
        }
        if (has[z] > 0) {
            // cout << "! " << i << " " << has[z] << "\n";
            gg[i].push_back(has[z]);
        }
    }
    
    vector<int> has2(n + 1);
    for (int i = 1; i <= m; ++i) {
        has2[x[i]] = i;
    }
    for (int i = 1; i <= m; ++i) {
        int z = lca(x[i], y[i]);
        int u = x[i];
        while (u != z) {
            if (has2[u] > 0) {
                // cout << "! " << has2[u] << " " << i << "\n";
                gg[has2[u]].push_back(i);
            }
            u = par[u];
        }
        u = y[i];
        while (u != z) {
            if (has2[u] > 0) {
                // cout << "! " << has2[u] << " " << i << "\n";
                gg[has2[u]].push_back(i);
            }
            u = par[u];
        }
        if (has2[z] > 0) {
            // cout << "! " << has2[z] << " " << i << "\n";
            gg[has2[z]].push_back(i);
        }
    }
    
    for (int i = 1; i <= n; ++i) vis[i] = 0;
    for (int i = 1; i <= m; ++i) {
        if (!vis[i]) {
            dfs2(i);
        }
    }
    reverse(ord.begin(), ord.end());

    vector<bool> blocked(n + 1, 0);
    for (int i = 1; i <= m; ++i) {
        blocked[x[i]] = 1;
    }

    bool good = 1;
    for (auto i : ord) {
        // cout << i << "\n";
        int z = lca(x[i], y[i]);
        int u = x[i];
        int cnt = 0;
        while (u != z) {
            cnt += blocked[u];
            u = par[u];
        }
        u = y[i];
        while (u != z) {
            cnt += blocked[u];
            u = par[u];
        }
        cnt += blocked[z];
        // cout << i << ": " << cnt << "\n";
        if (cnt > 1) {
            good = 0;
        }
        blocked[x[i]] = 0;
        blocked[y[i]] = 1;
    }
    
    cout << (good ? "Yes" : "No") << "\n";
    
    for (int i = 1; i <= n; ++i) {
        g[i].clear();
        gg[i].clear();
    }
    ord.clear();
}

/**
1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 5
2 6
3 7
4 8
**/

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int t; cin >> t;
    while (t--) solve();
}

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