Submission #545055

#	Time	Username	Problem	Language	Result	Execution time	Memory
545055		baluteshih	Jail (JOI22_jail)	C++14	100 / 100	712 ms	61816 KiB

jail

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

const int MAXN = 120005;
vector<int> G[MAXN];
int pa[MAXN], head[MAXN], sz[MAXN], dep[MAXN], dfn[MAXN], seq[MAXN], best[MAXN], dft;
int n;
pii walk[MAXN];

pii mem[MAXN * 100];
int memtop;
int tG[MAXN * 10], top, indeg[MAXN * 10];

struct Node {
    int up, dwn;
} seg[MAXN << 2];

void add_edge(int u, int v) {
    //cerr << "add_edge " << u << " " << v << "\n";
    mem[++memtop] = pii(tG[u], v);
    tG[u] = memtop;
    ++indeg[v];
}

void build(int l, int r, int rt) {
    if (l == r) {
        seg[rt].up = l;
        seg[rt].dwn = l + n;
        return;
    }
    seg[rt].up = ++top;
    indeg[top] = 0, tG[top] = 0;
    seg[rt].dwn = ++top;
    indeg[top] = 0, tG[top] = 0;
    //cerr << "[" << l << " " << r << "]: " << seg[rt].up << " " << seg[rt].dwn << "\n";
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
    add_edge(seg[rt << 1].up, seg[rt].up);
    add_edge(seg[rt << 1 | 1].up, seg[rt].up);
    add_edge(seg[rt].dwn, seg[rt << 1].dwn);
    add_edge(seg[rt].dwn, seg[rt << 1 | 1].dwn);
}

void modify(int L, int R, int l, int r, int rt, int up, int idx) {
    if (L <= l && R >= r) { 
        if (up)
            add_edge(seg[rt].up, idx);
        else
            add_edge(idx, seg[rt].dwn);
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid)
        modify(L, R, l, mid, rt << 1, up, idx);
    if (R > mid)
        modify(L, R, mid + 1, r, rt << 1 | 1, up, idx);
}

void dfs(int u, int f) {
    pa[u] = f;
    sz[u] = 1;
    best[u] = 0;
    for (int i : G[u])
        if (i != f) {
            dep[i] = dep[u] + 1;
            dfs(i, u);
            sz[u] += sz[i];
            if (sz[best[u]] < sz[i])
                best[u] = i;
        }
}

void dfs2(int u, int h) {
    head[u] = h;
    dfn[u] = ++dft;
    seq[dft] = u;
    if (best[u])
        dfs2(best[u], h);
    for (int i : G[u])
        if (i != pa[u] && i != best[u])
            dfs2(i, i);
}

void path_add(int u, int v, int up, int idx) {
    //cerr << "path_add " << u << " " << v << " " << up << " " << idx << "\n";
    int ban = v;
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]])
            swap(u, v);
        if (u != ban)
            modify(dfn[head[u]], dfn[u], 1, n, 1, up, idx);
        else if (dfn[head[u]] < dfn[u])
            modify(dfn[head[u]], dfn[u] - 1, 1, n, 1, up, idx);
        u = pa[head[u]];
    }
    if (dfn[u] > dfn[v])
        swap(u, v);
    if (u != ban && v != ban)
        modify(dfn[u], dfn[v], 1, n, 1, up, idx);
    else if (u == ban && dfn[u] < dfn[v])
        modify(dfn[u] + 1, dfn[v], 1, n, 1, up, idx);
    else if (v == ban && dfn[u] < dfn[v])
        modify(dfn[u], dfn[v] - 1, 1, n, 1, up, idx);
}

bool solve() {
    memtop = 0;
    int m;
    cin >> n, top = n * 2;
    for (int i = 1; i <= n; ++i)
        G[i].clear(), indeg[i] = tG[i] = indeg[i + n] = tG[i + n] = 0;
    build(1, n, 1);
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
    }
    dft = 0, dfs(1, 1), dfs2(1, 1);
    /*for (int i = 1; i <= n; ++i)
        cerr << seq[i] << " \n"[i == n];
    for (int i = 1; i <= n; ++i)
        cerr << head[i] << " \n"[i == n];*/
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        indeg[top + i] = tG[top + i] = 0;
        cin >> walk[i].X >> walk[i].Y;
    }
    for (int i = 1; i <= m; ++i) {
        add_edge(top + i, dfn[walk[i].X]);
        add_edge(dfn[walk[i].Y] + n, top + i);
    }
    for (int i = 1; i <= m; ++i) {
        int u = walk[i].X, v = walk[i].Y;
        path_add(u, v, 0, top + i);
        path_add(v, u, 1, top + i);
    }
    top += m;
    queue<int> q;
    for (int i = 1; i <= top; ++i)
        if (!indeg[i])
            q.push(i);
    while (!q.empty()) {
        int u = q.front();
        //cerr << "fin " << u << "\n";
        q.pop();
        while (tG[u] != 0) {
            if (!--indeg[mem[tG[u]].Y])
                q.push(mem[tG[u]].Y);
            tG[u] = mem[tG[u]].X;
        }
    }
    for (int i = 1; i <= top; ++i)
        if (indeg[i])
            return 0;
    return 1;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        if (solve())
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

• 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