oj.uz

Submission #1000508

# Submission time Handle Problem Language Result Execution time Memory
1000508 2024-06-17T16:03:51 Z onbert Jail (JOI22_jail) C++17
10 / 100
 2704 ms 1048580 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

void add(vector<pair<int,int>> &v, int L, int R) {
    if (v.size() > 0 && R+1 == v.back().first) v.back().first = L;
    else v.push_back({L, R});
}

const int maxn = 1e6+5, maxN = 4e6+5, lgn = 20, INF = 1e18;
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;
}
pair<int, vector<pair<int,int>>> binlift[maxn][lgn];
void dfs3(int u) {
    for (int i=1;i<lgn;i++) {
        if (binlift[u][i-1].first==-1 || binlift[binlift[u][i-1].first][i-1].first==-1) break;
        binlift[u][i].first = binlift[binlift[u][i-1].first][i-1].first;
        binlift[u][i].second = binlift[u][i-1].second;
        for (auto [L, R]:binlift[binlift[u][i-1].first][i-1].second) add(binlift[u][i].second, L, R);
    }
    for (int v:adj[u]) {
        binlift[v][0] = {u, {{u, u}}};
        dfs3(v);
    }
}
vector<pair<int,int>> PATH(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    vector<pair<int,int>> U = {{u, u}}, V = {{v, v}};
    for (int i=lgn-1;i>=0;i--) if (d[v] - (1<<i) >= d[u]) {
        for (auto [L, R]:binlift[v][i].second) add(V, L, R);
        v = binlift[v][i].first;
    }
    if (u==v) return V;
    for (int i=lgn-1;i>=0;i--) if (binlift[u][i].first != binlift[v][i].first) {
        for (auto [L, R]:binlift[u][i].second) add(U, L, R);
        u = binlift[u][i].first;
        for (auto [L, R]:binlift[v][i].second) add(V, L, R);
        v = binlift[v][i].first;
    }
    add(V, fa[v], fa[v]);
    for (auto [L, R]:U) V.push_back({L, R});
    return V;
}

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 addd) {
    if (r<findl || findr<l) return;
    if (findl<=l && r<=findr) {
        if (addd) seg[id].insert(val);
        else seg[id].erase(val);
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, val, addd);
    update(id*2+1, mid+1, r, findl, findr, val, addd);
}
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);
}

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

void dfs4(int u) {
    int s = a[u].first, t = a[u].second;
    vis[u] = 1;
    vector<pair<int,int>> path = PATH(s, t);
    for (auto [L, R]:path) {
        int cur = L-1;
        while (exist.size() > 0) {
            cur = *exist.upper_bound(cur);
            if (cur > R) break;
            if (cur==s) continue;
            int v = S[cur];
            // cout << u << " " << v << endl;
            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) {
        // cout << u << " " << v << endl;
        if (!vis[v]) dfs4(v);
        else if (vis[v]==1) die = true;
        if (die) return;
    }
    for (auto [L, R]:path) update(1, 1, n, 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]);
    for (int i=1;i<=n;i++) for (int j=0;j<lgn;j++) binlift[i][j] = {-1, {}};
    dfs3(1);
    // for (int i=1;i<=n;i++) {
    //     cout << i << endl;
    //     for (int j=0;j<lgn;j++) {
    //         cout << binlift[i][j].first << " ";
    //         for (auto [L, R]:binlift[i][j].second) cout << L << '.' << R << " ";
    //         cout << endl;
    //         if (binlift[i][j].first==-1) break;
    //     }
    //     cout << endl;
    // }
    // return;
    exist = {INF};
    build(1, 1, n);
    for (int i=1;i<=n;i++) S[i] = -1, T[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] = T[t] = i;
        exist.insert(s);
        vector<pair<int,int>> path = PATH(s, t);
        for (auto [L, R]:path) update(1, 1, n, 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 360 ms 863104 KB Output is correct
2 Correct 386 ms 862948 KB Output is correct
3 Correct 325 ms 863064 KB Output is correct
4 Correct 344 ms 863568 KB Output is correct
5 Correct 355 ms 863824 KB Output is correct
6 Correct 372 ms 863256 KB Output is correct
7 Correct 340 ms 863312 KB Output is correct
8 Correct 354 ms 863316 KB Output is correct
9 Correct 439 ms 868384 KB Output is correct
10 Correct 551 ms 953936 KB Output is correct
11 Correct 427 ms 863288 KB Output is correct
12 Correct 401 ms 864084 KB Output is correct
13 Correct 703 ms 974676 KB Output is correct
14 Correct 645 ms 973648 KB Output is correct
15 Correct 915 ms 992548 KB Output is correct
16 Correct 1843 ms 1047448 KB Output is correct
17 Correct 865 ms 1005140 KB Output is correct
18 Correct 629 ms 979540 KB Output is correct
19 Correct 767 ms 999188 KB Output is correct
20 Correct 754 ms 999256 KB Output is correct
21 Correct 784 ms 1004748 KB Output is correct
22 Correct 531 ms 962896 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 863192 KB Output is correct
2 Correct 396 ms 863060 KB Output is correct
3 Correct 397 ms 863316 KB Output is correct
4 Correct 351 ms 863224 KB Output is correct
5 Correct 361 ms 863196 KB Output is correct
6 Correct 362 ms 863240 KB Output is correct
7 Correct 337 ms 863320 KB Output is correct
8 Correct 368 ms 863188 KB Output is correct
9 Correct 362 ms 863188 KB Output is correct
10 Correct 378 ms 863316 KB Output is correct
11 Correct 324 ms 863316 KB Output is correct
12 Correct 359 ms 863152 KB Output is correct
13 Correct 363 ms 863172 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 863192 KB Output is correct
2 Correct 396 ms 863060 KB Output is correct
3 Correct 397 ms 863316 KB Output is correct
4 Correct 351 ms 863224 KB Output is correct
5 Correct 361 ms 863196 KB Output is correct
6 Correct 362 ms 863240 KB Output is correct
7 Correct 337 ms 863320 KB Output is correct
8 Correct 368 ms 863188 KB Output is correct
9 Correct 362 ms 863188 KB Output is correct
10 Correct 378 ms 863316 KB Output is correct
11 Correct 324 ms 863316 KB Output is correct
12 Correct 359 ms 863152 KB Output is correct
13 Correct 363 ms 863172 KB Output is correct
14 Correct 342 ms 863056 KB Output is correct
15 Correct 382 ms 863108 KB Output is correct
16 Correct 356 ms 863320 KB Output is correct
17 Correct 337 ms 863192 KB Output is correct
18 Correct 336 ms 863312 KB Output is correct
19 Correct 354 ms 863104 KB Output is correct
20 Correct 337 ms 863312 KB Output is correct
21 Correct 358 ms 863316 KB Output is correct
22 Correct 344 ms 863312 KB Output is correct
23 Correct 328 ms 863176 KB Output is correct
24 Runtime error 2583 ms 1048580 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 863192 KB Output is correct
2 Correct 396 ms 863060 KB Output is correct
3 Correct 397 ms 863316 KB Output is correct
4 Correct 351 ms 863224 KB Output is correct
5 Correct 361 ms 863196 KB Output is correct
6 Correct 362 ms 863240 KB Output is correct
7 Correct 337 ms 863320 KB Output is correct
8 Correct 368 ms 863188 KB Output is correct
9 Correct 362 ms 863188 KB Output is correct
10 Correct 378 ms 863316 KB Output is correct
11 Correct 324 ms 863316 KB Output is correct
12 Correct 359 ms 863152 KB Output is correct
13 Correct 363 ms 863172 KB Output is correct
14 Correct 342 ms 863056 KB Output is correct
15 Correct 382 ms 863108 KB Output is correct
16 Correct 356 ms 863320 KB Output is correct
17 Correct 337 ms 863192 KB Output is correct
18 Correct 336 ms 863312 KB Output is correct
19 Correct 354 ms 863104 KB Output is correct
20 Correct 337 ms 863312 KB Output is correct
21 Correct 358 ms 863316 KB Output is correct
22 Correct 344 ms 863312 KB Output is correct
23 Correct 328 ms 863176 KB Output is correct
24 Runtime error 2583 ms 1048580 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 863192 KB Output is correct
2 Correct 396 ms 863060 KB Output is correct
3 Correct 397 ms 863316 KB Output is correct
4 Correct 351 ms 863224 KB Output is correct
5 Correct 361 ms 863196 KB Output is correct
6 Correct 362 ms 863240 KB Output is correct
7 Correct 337 ms 863320 KB Output is correct
8 Correct 368 ms 863188 KB Output is correct
9 Correct 362 ms 863188 KB Output is correct
10 Correct 378 ms 863316 KB Output is correct
11 Correct 324 ms 863316 KB Output is correct
12 Correct 359 ms 863152 KB Output is correct
13 Correct 363 ms 863172 KB Output is correct
14 Correct 342 ms 863056 KB Output is correct
15 Correct 382 ms 863108 KB Output is correct
16 Correct 356 ms 863320 KB Output is correct
17 Correct 337 ms 863192 KB Output is correct
18 Correct 336 ms 863312 KB Output is correct
19 Correct 354 ms 863104 KB Output is correct
20 Correct 337 ms 863312 KB Output is correct
21 Correct 358 ms 863316 KB Output is correct
22 Correct 344 ms 863312 KB Output is correct
23 Correct 328 ms 863176 KB Output is correct
24 Runtime error 2583 ms 1048580 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 863096 KB Output is correct
2 Correct 373 ms 863056 KB Output is correct
3 Correct 329 ms 863192 KB Output is correct
4 Correct 345 ms 863312 KB Output is correct
5 Correct 325 ms 863184 KB Output is correct
6 Correct 352 ms 863132 KB Output is correct
7 Correct 381 ms 863060 KB Output is correct
8 Correct 369 ms 863060 KB Output is correct
9 Correct 390 ms 863060 KB Output is correct
10 Runtime error 2704 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 863104 KB Output is correct
2 Correct 386 ms 862948 KB Output is correct
3 Correct 325 ms 863064 KB Output is correct
4 Correct 344 ms 863568 KB Output is correct
5 Correct 355 ms 863824 KB Output is correct
6 Correct 372 ms 863256 KB Output is correct
7 Correct 340 ms 863312 KB Output is correct
8 Correct 354 ms 863316 KB Output is correct
9 Correct 439 ms 868384 KB Output is correct
10 Correct 551 ms 953936 KB Output is correct
11 Correct 427 ms 863288 KB Output is correct
12 Correct 401 ms 864084 KB Output is correct
13 Correct 703 ms 974676 KB Output is correct
14 Correct 645 ms 973648 KB Output is correct
15 Correct 915 ms 992548 KB Output is correct
16 Correct 1843 ms 1047448 KB Output is correct
17 Correct 865 ms 1005140 KB Output is correct
18 Correct 629 ms 979540 KB Output is correct
19 Correct 767 ms 999188 KB Output is correct
20 Correct 754 ms 999256 KB Output is correct
21 Correct 784 ms 1004748 KB Output is correct
22 Correct 531 ms 962896 KB Output is correct
23 Correct 356 ms 863192 KB Output is correct
24 Correct 396 ms 863060 KB Output is correct
25 Correct 397 ms 863316 KB Output is correct
26 Correct 351 ms 863224 KB Output is correct
27 Correct 361 ms 863196 KB Output is correct
28 Correct 362 ms 863240 KB Output is correct
29 Correct 337 ms 863320 KB Output is correct
30 Correct 368 ms 863188 KB Output is correct
31 Correct 362 ms 863188 KB Output is correct
32 Correct 378 ms 863316 KB Output is correct
33 Correct 324 ms 863316 KB Output is correct
34 Correct 359 ms 863152 KB Output is correct
35 Correct 363 ms 863172 KB Output is correct
36 Correct 342 ms 863056 KB Output is correct
37 Correct 382 ms 863108 KB Output is correct
38 Correct 356 ms 863320 KB Output is correct
39 Correct 337 ms 863192 KB Output is correct
40 Correct 336 ms 863312 KB Output is correct
41 Correct 354 ms 863104 KB Output is correct
42 Correct 337 ms 863312 KB Output is correct
43 Correct 358 ms 863316 KB Output is correct
44 Correct 344 ms 863312 KB Output is correct
45 Correct 328 ms 863176 KB Output is correct
46 Runtime error 2583 ms 1048580 KB Execution killed with signal 9
47 Halted 0 ms 0 KB -