Submission #710529

#	Time	Username	Problem	Language	Result	Execution time	Memory
710529		becaido	Jail (JOI22_jail)	C++17	49 / 100	654 ms	584128 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)

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

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

int sz;
queue<int> q;
vector<int> edge[SIZE * H];
int h[SIZE], to[SIZE][H + 1];
int deg[SIZE * H], in[SIZE][H + 1], out[SIZE][H + 1]; // 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 (h[a] < h[b]) swap(a, b);
    a = jump(a, h[a] - h[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 (h[a] > h[c]) return to[a][0];
    return jump(b, h[b] - h[a] - 1);
}

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

void add(int pos, int k, int ty, int x) {
    int cnt = 0;
    while (k) {
        if (k & 1) {
            if (ty == 0) edge[out[pos][cnt]].pb(x);
            if (ty == 1) edge[x].pb(in[pos][cnt]);
            pos = to[pos][cnt];
        }
        cnt++;
        k >>= 1;
    }
}

void add_edge(int x, int a, int b, int ty) {
    int c = lca(a, b);
    add(a, h[a] - h[c] + 1, ty, x);
    add(b, h[b] - h[c] + 1, ty, x);
}

void solve() {
    cin >> n;
    FOR (i, 1, n) {
        adj[i].clear();
        edge[i].clear();
        deg[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 != to[pos][0]) {
            h[np] = h[pos] + 1;
            to[np][0] = pos;
            dfs(dfs, np);
        }
    };
    h[1] = 1;
    dfs(dfs, 1);
    sz = m;
    FOR (i, 1, n) {
        in[i][0] = newnode();
        out[i][0] = newnode();
    }
    FOR (j, 1, H) FOR (i, 1, n) {
        to[i][j] = to[to[i][j - 1]][j - 1];
        in[i][j] = newnode();
        out[i][j] = newnode();
        edge[in[i][j]].pb(in[i][j - 1]);
        edge[out[i][j - 1]].pb(out[i][j]);
        if (to[i][j - 1]) {
            edge[in[i][j]].pb(in[to[i][j - 1]][j - 1]);
            edge[out[to[i][j - 1]][j - 1]].pb(out[i][j]);
        }
    }
    FOR (i, 1, m) {
        edge[i].pb(out[s[i]][0]);
        edge[in[t[i]][0]].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: 0 / 11
• Subtask 7: 0 / 23