제출 #1168427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168427		aycnl	Jail (JOI22_jail)	C++20	100 / 100	741 ms	91388 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, cnt, c1, c2;
vi ke[maxN], adj[10*maxN];
int s[maxN], t[maxN];
int par[maxN], h[maxN], pos[maxN], top[maxN], sz[maxN];
int ps[maxN], pt[maxN];
int deg[10*maxN], vst[10*maxN];
int fn1[4*maxN], fn2[4*maxN];

void pre_dfs(int u) {
    sz[u] = 1;
    for (int v : ke[u]) if (v != par[u]) {
        par[v] = u;
        h[v] = h[u] + 1;
        pre_dfs(v);
        sz[u] += sz[v];
    }
}

void hld(int u, int tp) {
    pos[u] = ++tme;
    top[u] = tp;
    //cout << u << endl;

    int bigC = 0;
    for (int v : ke[u]) if (v != par[u]) {
        if (sz[v] > sz[bigC]) bigC = v;
    }
    if (bigC) hld(bigC, tp);
    for (int v : ke[u]) if (v != par[u]) {
        if (v != bigC) hld(v, v);
    }
}

void build1(int id, int l, int r) {
    fn1[id] = ++cnt;
    if (l == r) {
        if (ps[l]) {
            adj[ps[l]].pb(fn1[id]);
            deg[fn1[id]]++;
        }
        return;
    }

    int m = (l+r)/2;
    build1(id*2, l, m);
    build1(id*2+1, m+1, r);

    adj[fn1[id*2]].pb(fn1[id]);
    adj[fn1[id*2+1]].pb(fn1[id]);
    deg[fn1[id]] += 2;
}

void build2(int id, int l, int r) {
    fn2[id] = ++cnt;
    if (l == r) {
        if (pt[l]) {
            adj[fn2[id]].pb(pt[l]);
            deg[pt[l]]++;
        }
        return;
    }
    int m = (l+r)/2;
    build2(id*2, l, m);
    build2(id*2+1, m+1, r);
    adj[fn2[id]].pb(fn2[id*2]);
    adj[fn2[id]].pb(fn2[id*2+1]);
    deg[fn2[id*2]]++;
    deg[fn2[id*2+1]]++;
}

void f1add(int id, int l, int r, int i, int j, int x) {
    if (l > j || r < i) return;
    if (i <= l && r <= j) {
        adj[fn1[id]].pb(x);
        deg[x]++;
        return;
    }
    //cout << l << " " << r << endl;

    int m = (l+r)/2;
    f1add(id*2, l, m, i, j, x);
    f1add(id*2+1, m+1, r, i, j, x);
}

void f2add(int id, int l, int r, int i, int j, int x) {
    if (l > j || r < i) return;
    if (i <= l && r <= j) {
        adj[x].pb(fn2[id]);
        deg[fn2[id]]++;
        return;
    }

    int m = (l+r)/2;
    f2add(id*2, l, m, i, j, x);
    f2add(id*2+1, m+1, r, i, j, x);
}

void fquery(int u, int v, int i) {
    //cout << u << " " << v << endl;
    int x = u, y = v;
    //cout << u << " " << v << endl;
    while (top[x] != top[y]) {
        //cout << 1 << endl;
        if (h[top[x]] < h[top[y]]) swap(x, y);
        //cout << x << " " << y << endl;
        f1add(1, 1, n, pos[top[x]] + (top[x] == u), pos[x] - (x == u) , i);
        f2add(1, 1, n, pos[top[x]] + (top[x] == v), pos[x] - (x == v), i);
        x = par[top[x]];
    }
    //cout << u << " " << v << endl;
    if (pos[x] > pos[y]) swap(x, y);
    f1add(1, 1, n, pos[x] + (x == u), pos[y] - (y == u), i);
    f2add(1, 1, n, pos[x] + (x == v), pos[y] - (y == v), i);
}

void solve() {
    cin >> n;
    fto(i, 1, n) {
        ke[i].clear();
        ps[i] = pt[i] = 0;
    }
    fto(i, 1, n-1) {
        int u, v; cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    tme = 0;
    pre_dfs(1);
    hld(1, 1);

    cin >> m;
    fto(i, 1, m) {
        cin >> s[i] >> t[i];
        ps[pos[s[i]]] = i;
        pt[pos[t[i]]] = i;
    }
    fto(i, 1, 8*n + m) deg[i] = 0, adj[i].clear();
    cnt = m;
    build1(1, 1, n);
    build2(1, 1, n);

    //return;
    fto(i, 1, m) {
        //cout << i << endl;
        fquery(s[i], t[i], i);
    }

    int vis = 0;
    queue<int> q;
    fto(i, 1, cnt) if (!deg[i]) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        //cout << u << endl;
        ++vis;

        for (int v : adj[u]) {
            --deg[v];
            if (deg[v] == 0) q.push(v);
        }
    }
    //fto(i, 1, cnt) cout << deg[i] << " "; cout << endl;

    if (vis == cnt) {
        cout << "Yes" << endl;
    } else {
        //cout << vis << " " << cnt << endl;
        cout << "No" << 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: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23