oj.uz

Submission #1000620

# Submission time Handle Problem Language Result Execution time Memory
1000620 2024-06-18T04:18:21 Z onbert Jail (JOI22_jail) C++17
61 / 100
 5000 ms 163368 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;
void PATH(int u, int v) {
    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;
}

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);
        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 (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];
    vis[u] = 1;
    PATH(s, t);
    for (auto [L, R]:path) {
        int cur = L-1;
        while (exist.size() > 1) {
            cur = *exist.upper_bound(cur);
            if (cur > R) break;
            if (cur==s) continue;
            int v = S[cur];
            if (!vis[v]) dfs4(v);
            else if (vis[v]==1) die = true;
            if (die) return;
        }
    }
    nxt.clear();
    qry(1, 1, n, t);
    for (int v:nxt) if (v!=u) {
        if (!vis[v]) dfs4(v);
        else if (vis[v]==1) die = true;
        if (die) return;
    }
    int head = skip[t];
    pair<int,int> cur = {t, 0};
    while (chain[head].size() > 0) {
        cur = *chain[head].upper_bound(cur);
        if (cur.first == INF) break;
        if (cur.second == u) continue;
        int v = cur.second;
        if (!vis[v]) dfs4(v);
        else if (vis[v]==1) die = true;
        if (die) return;
    }
    for (auto [L, R]:path) UPDATE(L, R, u, 0);
    exist.erase(s);
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38808 KB Output is correct
2 Correct 6 ms 38732 KB Output is correct
3 Correct 6 ms 38748 KB Output is correct
4 Correct 14 ms 39004 KB Output is correct
5 Correct 23 ms 39580 KB Output is correct
6 Correct 7 ms 38748 KB Output is correct
7 Correct 6 ms 38748 KB Output is correct
8 Correct 8 ms 38748 KB Output is correct
9 Correct 38 ms 41596 KB Output is correct
10 Correct 54 ms 66900 KB Output is correct
11 Correct 12 ms 38740 KB Output is correct
12 Correct 45 ms 39576 KB Output is correct
13 Correct 173 ms 87176 KB Output is correct
14 Correct 158 ms 87848 KB Output is correct
15 Correct 298 ms 106772 KB Output is correct
16 Correct 1018 ms 163368 KB Output is correct
17 Execution timed out 5053 ms 118100 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38744 KB Output is correct
2 Correct 6 ms 38748 KB Output is correct
3 Correct 6 ms 38892 KB Output is correct
4 Correct 7 ms 38748 KB Output is correct
5 Correct 7 ms 38744 KB Output is correct
6 Correct 7 ms 38748 KB Output is correct
7 Correct 7 ms 38748 KB Output is correct
8 Correct 7 ms 38748 KB Output is correct
9 Correct 7 ms 38748 KB Output is correct
10 Correct 7 ms 38816 KB Output is correct
11 Correct 7 ms 38748 KB Output is correct
12 Correct 7 ms 38716 KB Output is correct
13 Correct 6 ms 38716 KB Output is correct
14 Correct 6 ms 38744 KB Output is correct
15 Correct 6 ms 38804 KB Output is correct
16 Correct 7 ms 38748 KB Output is correct
17 Correct 7 ms 38876 KB Output is correct
18 Correct 7 ms 38748 KB Output is correct
19 Correct 6 ms 38748 KB Output is correct
20 Correct 8 ms 38748 KB Output is correct
21 Correct 7 ms 38748 KB Output is correct
22 Correct 6 ms 38748 KB Output is correct
23 Correct 6 ms 38748 KB Output is correct
24 Correct 6 ms 38724 KB Output is correct
25 Correct 7 ms 38748 KB Output is correct
26 Correct 6 ms 38748 KB Output is correct
27 Correct 7 ms 38736 KB Output is correct
28 Correct 6 ms 39004 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38744 KB Output is correct
2 Correct 6 ms 38748 KB Output is correct
3 Correct 6 ms 38892 KB Output is correct
4 Correct 7 ms 38748 KB Output is correct
5 Correct 7 ms 38744 KB Output is correct
6 Correct 7 ms 38748 KB Output is correct
7 Correct 7 ms 38748 KB Output is correct
8 Correct 7 ms 38748 KB Output is correct
9 Correct 7 ms 38748 KB Output is correct
10 Correct 7 ms 38816 KB Output is correct
11 Correct 7 ms 38748 KB Output is correct
12 Correct 7 ms 38716 KB Output is correct
13 Correct 6 ms 38716 KB Output is correct
14 Correct 6 ms 38744 KB Output is correct
15 Correct 6 ms 38804 KB Output is correct
16 Correct 7 ms 38748 KB Output is correct
17 Correct 7 ms 38876 KB Output is correct
18 Correct 7 ms 38748 KB Output is correct
19 Correct 6 ms 38748 KB Output is correct
20 Correct 8 ms 38748 KB Output is correct
21 Correct 7 ms 38748 KB Output is correct
22 Correct 6 ms 38748 KB Output is correct
23 Correct 6 ms 38748 KB Output is correct
24 Correct 6 ms 38724 KB Output is correct
25 Correct 7 ms 38748 KB Output is correct
26 Correct 6 ms 38748 KB Output is correct
27 Correct 7 ms 38736 KB Output is correct
28 Correct 6 ms 39004 KB Output is correct
29 Correct 10 ms 38744 KB Output is correct
30 Correct 7 ms 38752 KB Output is correct
31 Correct 9 ms 38744 KB Output is correct
32 Correct 8 ms 38744 KB Output is correct
33 Correct 7 ms 38748 KB Output is correct
34 Correct 8 ms 38912 KB Output is correct
35 Correct 8 ms 38760 KB Output is correct
36 Correct 8 ms 38748 KB Output is correct
37 Correct 8 ms 38744 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38744 KB Output is correct
2 Correct 6 ms 38748 KB Output is correct
3 Correct 6 ms 38892 KB Output is correct
4 Correct 7 ms 38748 KB Output is correct
5 Correct 7 ms 38744 KB Output is correct
6 Correct 7 ms 38748 KB Output is correct
7 Correct 7 ms 38748 KB Output is correct
8 Correct 7 ms 38748 KB Output is correct
9 Correct 7 ms 38748 KB Output is correct
10 Correct 7 ms 38816 KB Output is correct
11 Correct 7 ms 38748 KB Output is correct
12 Correct 7 ms 38716 KB Output is correct
13 Correct 6 ms 38716 KB Output is correct
14 Correct 6 ms 38744 KB Output is correct
15 Correct 6 ms 38804 KB Output is correct
16 Correct 7 ms 38748 KB Output is correct
17 Correct 7 ms 38876 KB Output is correct
18 Correct 7 ms 38748 KB Output is correct
19 Correct 6 ms 38748 KB Output is correct
20 Correct 8 ms 38748 KB Output is correct
21 Correct 7 ms 38748 KB Output is correct
22 Correct 6 ms 38748 KB Output is correct
23 Correct 6 ms 38748 KB Output is correct
24 Correct 6 ms 38724 KB Output is correct
25 Correct 7 ms 38748 KB Output is correct
26 Correct 6 ms 38748 KB Output is correct
27 Correct 7 ms 38736 KB Output is correct
28 Correct 6 ms 39004 KB Output is correct
29 Correct 10 ms 38744 KB Output is correct
30 Correct 7 ms 38752 KB Output is correct
31 Correct 9 ms 38744 KB Output is correct
32 Correct 8 ms 38744 KB Output is correct
33 Correct 7 ms 38748 KB Output is correct
34 Correct 8 ms 38912 KB Output is correct
35 Correct 8 ms 38760 KB Output is correct
36 Correct 8 ms 38748 KB Output is correct
37 Correct 8 ms 38744 KB Output is correct
38 Correct 39 ms 41584 KB Output is correct
39 Correct 55 ms 66896 KB Output is correct
40 Correct 43 ms 41300 KB Output is correct
41 Correct 51 ms 40788 KB Output is correct
42 Correct 41 ms 41296 KB Output is correct
43 Correct 27 ms 40788 KB Output is correct
44 Correct 26 ms 39512 KB Output is correct
45 Correct 62 ms 52048 KB Output is correct
46 Correct 61 ms 52048 KB Output is correct
47 Correct 48 ms 59220 KB Output is correct
48 Correct 53 ms 59216 KB Output is correct
49 Correct 53 ms 52552 KB Output is correct
50 Correct 50 ms 52560 KB Output is correct
51 Correct 46 ms 54100 KB Output is correct
52 Correct 44 ms 54104 KB Output is correct
53 Correct 22 ms 39936 KB Output is correct
54 Correct 58 ms 52052 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38744 KB Output is correct
2 Correct 7 ms 38748 KB Output is correct
3 Correct 6 ms 38740 KB Output is correct
4 Correct 7 ms 38808 KB Output is correct
5 Correct 11 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 8 ms 38736 KB Output is correct
9 Correct 7 ms 38748 KB Output is correct
10 Correct 6 ms 38812 KB Output is correct
11 Correct 6 ms 38748 KB Output is correct
12 Correct 8 ms 38744 KB Output is correct
13 Incorrect 31 ms 39240 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 38808 KB Output is correct
2 Correct 6 ms 38732 KB Output is correct
3 Correct 6 ms 38748 KB Output is correct
4 Correct 14 ms 39004 KB Output is correct
5 Correct 23 ms 39580 KB Output is correct
6 Correct 7 ms 38748 KB Output is correct
7 Correct 6 ms 38748 KB Output is correct
8 Correct 8 ms 38748 KB Output is correct
9 Correct 38 ms 41596 KB Output is correct
10 Correct 54 ms 66900 KB Output is correct
11 Correct 12 ms 38740 KB Output is correct
12 Correct 45 ms 39576 KB Output is correct
13 Correct 173 ms 87176 KB Output is correct
14 Correct 158 ms 87848 KB Output is correct
15 Correct 298 ms 106772 KB Output is correct
16 Correct 1018 ms 163368 KB Output is correct
17 Execution timed out 5053 ms 118100 KB Time limit exceeded
18 Halted 0 ms 0 KB -