Submission #1168026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168026		aycnl	Jail (JOI22_jail)	C++20	5 / 100	53 ms	29124 KiB

jail

#include <bits/stdc++.h>
using namespace std;

#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))

#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)

#define pb push_back
#define pf push_front

#define endl "\n"
#define oo (int)(1e9 + 7)
#define maxN 120005

#define l(s) s.length()

#define vi vector <int>
#define vii vector <ii>

#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)

#define EPS 1e-9
#define pi (acos(-1))
#define ll long long

int n, m, tme;
vi ke[maxN], topo;
int s[maxN], t[maxN];
int par[maxN], h[maxN];
int p[maxN], pos[maxN], vst[maxN];
int sta[maxN], fin[maxN], up[20][maxN];
int bt[maxN];

void ud(int i, int x) {
    for (; i <= n; i += (i & -i)) bt[i] += x;
}

int qry(int i) {
    int res = 0;
    for (; i; i -= (i & -i)) res += bt[i];
    return res;
}

void pre_dfs(int u) {
    sta[u] = ++tme;
    flto(j, 1, h[u]) up[j][u] = up[j-1][up[j-1][u]];
    for (int v : ke[u]) if (v != par[u]) {
        par[v] = u;
        h[v] = h[u] + 1;
        up[0][v] = u;
        pre_dfs(v);
    }
    fin[u] = tme;
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    fdto(i, 17, 0) if (h[u] - bit(i) >= h[v]) u = up[i][u];
    if (u == v) return u;
    fdto(i, 17, 0) if (up[i][u] != up[i][v]) u = up[i][u], v = up[i][v];
    return up[0][u];
}

int tqry(int u, int v) {
    //cout << u << " " << v << " " << lca(u, v) << endl;
    //cout << qry(sta[u]) << " " << qry(sta[v]) << " " << qry(sta[lca(u, v)]) << endl;
    int l = lca(u, v);
    int res = qry(sta[u]) + qry(sta[v]) - qry(sta[l]) - qry(sta[par[l]]);
    //cout << u << " " << v << " " << res << endl;
    //cout << l << " " << par[l] << endl;
    //cout << qry(sta[u]) << " " << qry(sta[v]) << " " <<  qry(sta[l]) << " " << qry(par[l]) << endl;
    return res;
}

int fSet(int u) {
    return p[u] == 0 ? u : p[u] = fSet(p[u]);
}

void uSet(int u, int v) {
    u = fSet(u);
    v = fSet(v);
    if (u == v) return;
    p[v] = u;
}

void dfs(int u) {
    vst[u] = 1;
    int a = fSet(s[u]), b = fSet(t[u]);
    while (a != b) {
        if (h[a] < h[b]) swap(a, b);
        uSet(par[a], a);
        if (pos[a] != 0 && pos[a] != u && !vst[pos[a]]) dfs(pos[a]);
        if (pos[par[a]] != 0 && pos[par[a]] != u && !vst[pos[par[a]]]) dfs(pos[par[a]]);
        a = fSet(a);
    }
    topo.pb(u);
}

void solve() {
    cin >> n;
    fto(i, 1, n) ke[i].clear(), pos[i] = 0, p[i] = 0, par[i] = 0, h[i] = 0, bt[i] = 0;
    topo.clear();
    fto(i, 1, n-1) {
        int u, v; cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    tme = 0;
    pre_dfs(1);

    cin >> m;
    fto(i, 1, m) {
        cin >> s[i] >> t[i];
        pos[s[i]] = i;
        //pos[t[i]] = i;
        vst[i] = 0;
    }
    fto(i, 1, m) if (!vst[i]) dfs(i);
    fto(i, 1, n) p[i] = 0;
    fto(i, 1, m) vst[i] = 1;

    for (int u : topo) {
        vst[u] = u;
        //cout << u << " ";
    }
    //cout << endl;
    for (int u : topo) {
        vst[u] = 0;
        int a = fSet(s[u]), b = fSet(t[u]);
        //cout << u << endl;
        if (tqry(s[u], t[u])) {
            //cout << u << endl;
            cout << "No" << endl;
            return;
        }
        //pos[t[u]] = u;

        while (a != b) {
            if (h[a] < h[b]) swap(a, b);
            uSet(par[a], a);
            //a = fSet(a);
            if (pos[a] != 0 && pos[a] != u && vst[pos[a]]) {
                cout << "No" << endl;
                return;
            }
            if (pos[par[a]] != 0 && pos[par[a]] != u && vst[pos[par[a]]]) {
                cout << "No" << endl;
                return;
            }
            a = fSet(a);
        }
        ud(sta[t[u]], 1);
        ud(fin[t[u]] + 1, -1);
    }
    cout << "Yes" << endl;
    //for (int u : topo) cout << u << " "; cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int test; cin >> test;
    while (test--) solve();

    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