oj.uz

Submission #1000634

# Submission time Handle Problem Language Result Execution time Memory
1000634 2024-06-18T05:02:46 Z onbert Jail (JOI22_jail) C++17
10 / 100
 959 ms 160596 KB 
#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(int u, int v) {
    vector<pair<int,int>> path;
    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;
    return path;
}

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);
}
void qry(int id, int l, int r, int &target, vector<int> &nxt) {
    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, nxt); qry(id*2+1, mid+1, r, target, nxt);
}

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;
    vector<pair<int,int>> path = 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;
        }
    }
    vector<int> nxt;
    qry(1, 1, n, t, nxt);
    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;
    }
    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);
        vector<pair<int,int>> path = 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38748 KB Output is correct
2 Correct 6 ms 38800 KB Output is correct
3 Correct 6 ms 38748 KB Output is correct
4 Correct 17 ms 38832 KB Output is correct
5 Correct 22 ms 38748 KB Output is correct
6 Correct 6 ms 38748 KB Output is correct
7 Correct 7 ms 38744 KB Output is correct
8 Correct 8 ms 38748 KB Output is correct
9 Correct 41 ms 40312 KB Output is correct
10 Correct 50 ms 65540 KB Output is correct
11 Correct 11 ms 38748 KB Output is correct
12 Correct 52 ms 38816 KB Output is correct
13 Correct 161 ms 85844 KB Output is correct
14 Correct 112 ms 85840 KB Output is correct
15 Correct 391 ms 104788 KB Output is correct
16 Correct 959 ms 160596 KB Output is correct
17 Correct 286 ms 117584 KB Output is correct
18 Correct 221 ms 95312 KB Output is correct
19 Correct 253 ms 111444 KB Output is correct
20 Correct 206 ms 111440 KB Output is correct
21 Correct 258 ms 116932 KB Output is correct
22 Correct 94 ms 73556 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38744 KB Output is correct
2 Correct 5 ms 38748 KB Output is correct
3 Correct 6 ms 38772 KB Output is correct
4 Correct 6 ms 38816 KB Output is correct
5 Correct 7 ms 38744 KB Output is correct
6 Correct 6 ms 38748 KB Output is correct
7 Correct 7 ms 38752 KB Output is correct
8 Correct 6 ms 38720 KB Output is correct
9 Correct 6 ms 38748 KB Output is correct
10 Correct 6 ms 38748 KB Output is correct
11 Correct 7 ms 38760 KB Output is correct
12 Correct 6 ms 38744 KB Output is correct
13 Correct 6 ms 38748 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38744 KB Output is correct
2 Correct 5 ms 38748 KB Output is correct
3 Correct 6 ms 38772 KB Output is correct
4 Correct 6 ms 38816 KB Output is correct
5 Correct 7 ms 38744 KB Output is correct
6 Correct 6 ms 38748 KB Output is correct
7 Correct 7 ms 38752 KB Output is correct
8 Correct 6 ms 38720 KB Output is correct
9 Correct 6 ms 38748 KB Output is correct
10 Correct 6 ms 38748 KB Output is correct
11 Correct 7 ms 38760 KB Output is correct
12 Correct 6 ms 38744 KB Output is correct
13 Correct 6 ms 38748 KB Output is correct
14 Correct 6 ms 38800 KB Output is correct
15 Correct 6 ms 38748 KB Output is correct
16 Correct 7 ms 38748 KB Output is correct
17 Correct 7 ms 38748 KB Output is correct
18 Correct 7 ms 38748 KB Output is correct
19 Correct 6 ms 38744 KB Output is correct
20 Correct 7 ms 38748 KB Output is correct
21 Correct 7 ms 38748 KB Output is correct
22 Correct 7 ms 38748 KB Output is correct
23 Correct 6 ms 38748 KB Output is correct
24 Correct 6 ms 38748 KB Output is correct
25 Correct 7 ms 38748 KB Output is correct
26 Correct 6 ms 38748 KB Output is correct
27 Incorrect 7 ms 38748 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38744 KB Output is correct
2 Correct 5 ms 38748 KB Output is correct
3 Correct 6 ms 38772 KB Output is correct
4 Correct 6 ms 38816 KB Output is correct
5 Correct 7 ms 38744 KB Output is correct
6 Correct 6 ms 38748 KB Output is correct
7 Correct 7 ms 38752 KB Output is correct
8 Correct 6 ms 38720 KB Output is correct
9 Correct 6 ms 38748 KB Output is correct
10 Correct 6 ms 38748 KB Output is correct
11 Correct 7 ms 38760 KB Output is correct
12 Correct 6 ms 38744 KB Output is correct
13 Correct 6 ms 38748 KB Output is correct
14 Correct 6 ms 38800 KB Output is correct
15 Correct 6 ms 38748 KB Output is correct
16 Correct 7 ms 38748 KB Output is correct
17 Correct 7 ms 38748 KB Output is correct
18 Correct 7 ms 38748 KB Output is correct
19 Correct 6 ms 38744 KB Output is correct
20 Correct 7 ms 38748 KB Output is correct
21 Correct 7 ms 38748 KB Output is correct
22 Correct 7 ms 38748 KB Output is correct
23 Correct 6 ms 38748 KB Output is correct
24 Correct 6 ms 38748 KB Output is correct
25 Correct 7 ms 38748 KB Output is correct
26 Correct 6 ms 38748 KB Output is correct
27 Incorrect 7 ms 38748 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38744 KB Output is correct
2 Correct 5 ms 38748 KB Output is correct
3 Correct 6 ms 38772 KB Output is correct
4 Correct 6 ms 38816 KB Output is correct
5 Correct 7 ms 38744 KB Output is correct
6 Correct 6 ms 38748 KB Output is correct
7 Correct 7 ms 38752 KB Output is correct
8 Correct 6 ms 38720 KB Output is correct
9 Correct 6 ms 38748 KB Output is correct
10 Correct 6 ms 38748 KB Output is correct
11 Correct 7 ms 38760 KB Output is correct
12 Correct 6 ms 38744 KB Output is correct
13 Correct 6 ms 38748 KB Output is correct
14 Correct 6 ms 38800 KB Output is correct
15 Correct 6 ms 38748 KB Output is correct
16 Correct 7 ms 38748 KB Output is correct
17 Correct 7 ms 38748 KB Output is correct
18 Correct 7 ms 38748 KB Output is correct
19 Correct 6 ms 38744 KB Output is correct
20 Correct 7 ms 38748 KB Output is correct
21 Correct 7 ms 38748 KB Output is correct
22 Correct 7 ms 38748 KB Output is correct
23 Correct 6 ms 38748 KB Output is correct
24 Correct 6 ms 38748 KB Output is correct
25 Correct 7 ms 38748 KB Output is correct
26 Correct 6 ms 38748 KB Output is correct
27 Incorrect 7 ms 38748 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38748 KB Output is correct
2 Correct 6 ms 38804 KB Output is correct
3 Correct 6 ms 38748 KB Output is correct
4 Correct 6 ms 38736 KB Output is correct
5 Correct 12 ms 38748 KB Output is correct
6 Correct 6 ms 38748 KB Output is correct
7 Correct 6 ms 38748 KB Output is correct
8 Correct 7 ms 38740 KB Output is correct
9 Correct 6 ms 38748 KB Output is correct
10 Correct 6 ms 38736 KB Output is correct
11 Correct 6 ms 38744 KB Output is correct
12 Correct 9 ms 38744 KB Output is correct
13 Incorrect 32 ms 38748 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38748 KB Output is correct
2 Correct 6 ms 38800 KB Output is correct
3 Correct 6 ms 38748 KB Output is correct
4 Correct 17 ms 38832 KB Output is correct
5 Correct 22 ms 38748 KB Output is correct
6 Correct 6 ms 38748 KB Output is correct
7 Correct 7 ms 38744 KB Output is correct
8 Correct 8 ms 38748 KB Output is correct
9 Correct 41 ms 40312 KB Output is correct
10 Correct 50 ms 65540 KB Output is correct
11 Correct 11 ms 38748 KB Output is correct
12 Correct 52 ms 38816 KB Output is correct
13 Correct 161 ms 85844 KB Output is correct
14 Correct 112 ms 85840 KB Output is correct
15 Correct 391 ms 104788 KB Output is correct
16 Correct 959 ms 160596 KB Output is correct
17 Correct 286 ms 117584 KB Output is correct
18 Correct 221 ms 95312 KB Output is correct
19 Correct 253 ms 111444 KB Output is correct
20 Correct 206 ms 111440 KB Output is correct
21 Correct 258 ms 116932 KB Output is correct
22 Correct 94 ms 73556 KB Output is correct
23 Correct 6 ms 38744 KB Output is correct
24 Correct 5 ms 38748 KB Output is correct
25 Correct 6 ms 38772 KB Output is correct
26 Correct 6 ms 38816 KB Output is correct
27 Correct 7 ms 38744 KB Output is correct
28 Correct 6 ms 38748 KB Output is correct
29 Correct 7 ms 38752 KB Output is correct
30 Correct 6 ms 38720 KB Output is correct
31 Correct 6 ms 38748 KB Output is correct
32 Correct 6 ms 38748 KB Output is correct
33 Correct 7 ms 38760 KB Output is correct
34 Correct 6 ms 38744 KB Output is correct
35 Correct 6 ms 38748 KB Output is correct
36 Correct 6 ms 38800 KB Output is correct
37 Correct 6 ms 38748 KB Output is correct
38 Correct 7 ms 38748 KB Output is correct
39 Correct 7 ms 38748 KB Output is correct
40 Correct 7 ms 38748 KB Output is correct
41 Correct 6 ms 38744 KB Output is correct
42 Correct 7 ms 38748 KB Output is correct
43 Correct 7 ms 38748 KB Output is correct
44 Correct 7 ms 38748 KB Output is correct
45 Correct 6 ms 38748 KB Output is correct
46 Correct 6 ms 38748 KB Output is correct
47 Correct 7 ms 38748 KB Output is correct
48 Correct 6 ms 38748 KB Output is correct
49 Incorrect 7 ms 38748 KB Output isn't correct
50 Halted 0 ms 0 KB -