Submission #710497

#	Time	Username	Problem	Language	Result	Execution time	Memory
710497		becaido	Jail (JOI22_jail)	C++17	60 / 100	5055 ms	263400 KiB

jail

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

// s[i] lies on path(s[j], t[j]), build an edge(i -> j)
// t[i] lies on path(s[j], t[j]), build an edge(j -> i)

#define lpos pos*2
#define rpos pos*2+1

const int SIZE = 1.2e5 + 5;
const int H = __lg(SIZE) + 1;

int n, m;
int s[SIZE], t[SIZE];
vector<int> adj[SIZE];

int dfsid, id[SIZE], to[SIZE][H + 1];
int w[SIZE], dep[SIZE], pa[SIZE], son[SIZE], tp[SIZE];

int sz, deg[6 * SIZE];
queue<int> q;
vector<int> edge[6 * SIZE];
int nid[SIZE], in[4 * SIZE], out[4 * SIZE]; // in : large to small, out : small to large

int jump(int pos, int k) {
    int cnt = 0;
    while (k) {
        if (k & 1) pos = to[pos][cnt];
        cnt++;
        k >>= 1;
    }
    return pos;
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    a = jump(a, dep[a] - dep[b]);
    if (a == b) return a;
    for (int i = H; i >= 0; i--) if (to[a][i] != to[b][i]) {
        a = to[a][i];
        b = to[b][i];
    }
    return to[a][0];
}

int walk(int a, int b) {
    int c = lca(a, b);
    if (dep[a] > dep[c]) return pa[a];
    return jump(b, dep[b] - dep[a] - 1);
}

int newnode() {
    sz++;
    deg[sz] = 0;
    edge[sz].clear();
    return sz;
}

void build(int pos, int l, int r) {
    in[pos] = newnode();
    out[pos] = newnode();
    if (l == r) {
        nid[l] = pos;
        return;
    }
    int mid = (l + r) / 2;
    build(lpos, l, mid);
    build(rpos, mid + 1, r);

    edge[in[pos]].pb(in[lpos]);
    edge[in[pos]].pb(in[rpos]);
    edge[out[lpos]].pb(out[pos]);
    edge[out[rpos]].pb(out[pos]);
}

void add(int pos, int l, int r, int L, int R, int ty, int x) {
    if (l == L && r == R) {
        if (ty == 0) edge[out[pos]].pb(x);
        if (ty == 1) edge[x].pb(in[pos]);
        return;
    }
    int mid = (L + R) / 2;
    if (r <= mid) add(lpos, l, r, L, mid, ty, x);
    else if (l > mid) add(rpos, l, r, mid + 1, R, ty, x);
    else {
        add(lpos, l, mid, L, mid, ty, x);
        add(rpos, mid + 1, r, mid + 1, R, ty, x);
    }
}

void add_edge(int x, int a, int b, int ty) {
    while (tp[a] != tp[b]) {
        if (dep[tp[a]] < dep[tp[b]]) swap(a, b);
        add(1, id[tp[a]], id[a], 1, n, ty, x);
        a = pa[tp[a]];
    }
    if (dep[a] > dep[b]) swap(a, b);
    add(1, id[a], id[b], 1, n, ty, x);
}

void solve() {
    cin >> n;
    FOR (i, 1, n) {
        adj[i].clear();
        edge[i].clear();
        deg[i] = son[i] = tp[i] = 0;
    }
    FOR (i, 2, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    cin >> m;
    FOR (i, 1, m) cin >> s[i] >> t[i];

    auto dfs = [&](auto dfs, int pos)->void {
        for (int np : adj[pos]) if (np != pa[pos]) {
            dep[np] = dep[pos] + 1;
            pa[np] = to[np][0] = pos;
            dfs(dfs, np);
            w[pos] += w[np];
            if (w[np] > w[son[pos]]) son[pos] = np;
        }
    };
    dep[1] = 1;
    dfs(dfs, 1);
    FOR (j, 1, H) FOR (i, 1, n) to[i][j] = to[to[i][j - 1]][j - 1];

    dfsid = 0;
    auto dfs2 = [&](auto dfs2, int pos)->void {
        id[pos] = ++dfsid;
        if (!tp[pos]) tp[pos] = pos;
        if (son[pos]) {
            tp[son[pos]] = tp[pos];
            dfs2(dfs2, son[pos]);
        }
        for (int np : adj[pos]) if (np != pa[pos] && np != son[pos]) dfs2(dfs2, np);
    };
    dfs2(dfs2, 1);

    sz = m;
    build(1, 1, n);
    FOR (i, 1, m) {
        edge[i].pb(out[nid[id[s[i]]]]);
        edge[in[nid[id[t[i]]]]].pb(i);
    }
    FOR (i, 1, m) {
        add_edge(i, walk(s[i], t[i]), t[i], 0);
        add_edge(i, s[i], walk(t[i], s[i]), 1);
    }

    FOR (i, 1, sz) for (int j : edge[i]) deg[j]++;
    FOR (i, 1, sz) if (!deg[i]) q.push(i);
    int cnt = 0;
    while (q.size()) {
        int pos = q.front();
        q.pop();
        cnt++;
        for (int np : edge[pos]) if (--deg[np] == 0) q.push(np);
    }
    cout << (cnt == sz ? "Yes" : "No") << '\n';
}

int main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) solve();
}

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