Submission #1000628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000628		onbert	Jail (JOI22_jail)	C++17	10 / 100	999 ms	160396 KiB

jail

#include <bits/stdc++.h>
using namespace std;
const int maxn = 120005, maxN = 480005, lgn = 17, INF = 1e6;
int n, m;
vector<int> ADJ[maxn], adj[maxn];
pair<int,int> a[maxn];
int sz[maxn], fa[maxn], d[maxn], newid[maxn], lim[maxn], cnter = 0;

bool cmp(int &x, int &y) {
    return sz[x] > sz[y];
}

void dfs1(int u) {
    sz[u] = 1;
    for (int v:ADJ[u]) {
        ADJ[v].erase(find(ADJ[v].begin(), ADJ[v].end(), u));
        dfs1(v);
        sz[u] += sz[v];
    }
    sort(ADJ[u].begin(), ADJ[u].end(), cmp);
}
void dfs2(int u) {
    cnter++;
    newid[u] = cnter;
    for (int v:ADJ[u]) {
        d[cnter+1] = d[newid[u]] + 1;
        fa[cnter+1] = newid[u];
        dfs2(v);
    }
    lim[newid[u]] = cnter;
}

int skip[maxn];
void dfs3(int u) {
    for (int v:adj[u]) {
        if (v == adj[u][0]) skip[v] = skip[u];
        else skip[v] = v;
        dfs3(v);
    }
}

vector<pair<int,int>> path;
void PATH(int u, int v) {
    // bool TEST = (u == a[3].first && v == a[3].second);
    path.clear();
    if (d[u] > d[v]) swap(u, v);
    path = {{skip[u], u}};
    u = skip[u];
    while (u>v || v>lim[u]) {
        u = fa[u];
        path.push_back({skip[u], u});
        u = skip[u];
    }
    auto [l, r] = path.back();
    while (l<r) {
        int mid = (l+r+1)/2;
        if (mid<=v && v<=lim[mid]) l = mid;
        else r = mid-1;
    }
    path.back().first = u = l;
    path.push_back({skip[v], v});
    v = skip[v];
    while (d[fa[v]] > d[u]) {
        v = fa[v];
        path.push_back({skip[v], v});
        v = skip[v];
    }
    path.back().first += d[u] - d[v] + 1;
    // if (TEST) {
    //     cout << "PATH\n";
    //     for (auto [L, R]:path) cout << L << " " << R << endl;
    // }
}

set<pair<int,int>> chain[maxn];

set<int> seg[maxN];
void build(int id, int l, int r) {
    seg[id].clear();
    if (l==r) return;
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void update(int id, int l, int r, int &findl, int &findr, int &val, bool psh) {
    if (r<findl || findr<l) return;
    if (findl<=l && r<=findr) {
        if (psh) seg[id].insert(val);
        else seg[id].erase(val);
        // if (val == 3) cout << l << " " << r << " " << psh << endl;
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, val, psh);
    update(id*2+1, mid+1, r, findl, findr, val, psh);
}
vector<int> nxt;
void qry(int id, int l, int r, int &target) {
    if (r<target || target<l) return;
    for (int i:seg[id]) nxt.push_back(i);
    if (l==r) return;
    int mid = (l+r)/2;
    qry(id*2, l, mid, target); qry(id*2+1, mid+1, r, target);
}

void UPDATE(int l, int r, int val, int psh) {
    // if (val == 3) cout << "test " << l << " " << r << " " << psh << endl;
    if (l==skip[l]) {
        if (psh) chain[l].insert({r, val});
        else chain[l].erase({r, val});
        // cout << l << " " << r << " " << val << " " << psh << endl;
    } else update(1, 1, n, l, r, val, psh);
}

int S[maxn], vis[maxn];
bool die = false;
set<int> exist;

void dfs4(int u) {
    auto [s, t] = a[u];
    // cout << "start " << u << " " << s << " " << t << endl;
    vis[u] = 1;
    PATH(s, t);
    for (auto [L, R]:path) {
        int cur = L-1;
        while (true) {
            cur = *exist.upper_bound(cur);
            if (cur > R) break;
            if (cur==s) continue;
            int v = S[cur];
            // cout << "1 " << u << " " << v << " " << die << endl;
            if (!vis[v]) dfs4(v);
            else die = true;
            if (die) return;
        }
    }
    nxt.clear();
    qry(1, 1, n, t);
    for (int v:nxt) if (v!=u) {
        // cout << "2 " << u << " " << v << " " << die << endl;
        if (!vis[v]) dfs4(v);
        else die = true;
        if (die) return;
    }
    int head = skip[t];
    pair<int,int> cur = {t, 0};
    while (true) {
        cur = *chain[head].upper_bound(cur);
        if (cur.first == INF) break;
        if (cur.second == u) continue;
        int v = cur.second;
        // cout << "3 " << u << " " << v << " " << die << endl;
        if (!vis[v]) dfs4(v);
        else die = true;
        if (die) return;
    }
    PATH(s, t);
    for (auto [L, R]:path) UPDATE(L, R, u, 0);
    exist.erase(s);
    // cout << "killed " << u << endl;
    // vis[u] = 2;
}

void solve() {
    cin >> n;
    for (int i=1;i<=n;i++) sz[i] = 0, adj[i].clear(), ADJ[i].clear();
    cnter = 0;
    for (int i=1;i<=n-1;i++) {
        int u, v;
        cin >> u >> v;
        ADJ[u].push_back(v);
        ADJ[v].push_back(u);
    }
    fa[1] = 0, d[1] = 0;
    dfs1(1); dfs2(1);
    for (int i=1;i<=n;i++) for (int j:ADJ[i]) adj[newid[i]].push_back(newid[j]);
    skip[1] = 1;
    dfs3(1);
    exist = {INF};
    build(1, 1, n);
    for (int i=1;i<=n;i++) chain[i] = {{INF, INF}}, S[i] = -1;
    cin >> m;
    for (int i=1;i<=m;i++) {
        int s, t;
        cin >> s >> t;
        s = newid[s], t = newid[t];
        a[i] = {s, t};
        S[s] = i;
        exist.insert(s);
        PATH(s, t);
        for (auto [L, R]:path) UPDATE(L, R, i, 1);
    }
    for (int i=1;i<=m;i++) vis[i] = 0;
    die = false;
    for (int i=1;i<=m;i++) if (!vis[i]) {
        dfs4(i);
        if (die) break;
    }
    if (die) cout << "No\n";
    else cout << "Yes\n";
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

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