oj.uz

Submission #531953

# Submission time Handle Problem Language Result Execution time Memory
531953 2022-03-02T01:26:39 Z 4fecta Inside information (BOI21_servers) C++17
52.5 / 100
 351 ms 150908 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

struct query {
    int t, u, v, i;
};

const int MN = 240005;

int n, q, u, v, sz[MN], vis[MN], num[MN], inc[MN], des[MN], id, top[MN], ans[MN], pre[MN], par[MN], freq[MN];
char c;
vector<int> nodes[MN];
vector<pii> a[MN];
vector<query> ch[MN * 10];

int size_of(int cur, int par) {
    sz[cur] = 1;
    for (pii nxt : a[cur]) {
        if (vis[nxt.f] || nxt.f == par) continue;
        sz[cur] += size_of(nxt.f, cur);
    }
    return sz[cur];
}

int get_centroid(int cur, int par, int cnt) {
    for (pii nxt : a[cur]) {
        if (vis[nxt.f] || nxt.f == par) continue;
        if (sz[nxt.f] > cnt) return get_centroid(nxt.f, cur, cnt);
    }
    return cur;
}

void dfs(int cur, int par, int len, int col, int D, int I, int T) {
    num[cur] = col;
    des[cur] = D;
    inc[cur] = I;
    top[cur] = T;
    pre[cur] = len;
    for (pii nxt : a[cur]) {
        if (vis[nxt.f] || nxt.f == par) continue;
        dfs(nxt.f, cur, nxt.s, col, D & (nxt.s < len), I & (nxt.s > len), T);
    }
}

void solve(int cur, vector<query> qs) {
    cur = get_centroid(cur, 0, size_of(cur, 0) / 2);
    //printf("%lld\n", cur);
    for (pii nxt : a[cur]) {
        if (vis[nxt.f]) continue;
        ch[++id].clear();
        dfs(nxt.f, cur, nxt.s, id, 1, 1, nxt.s);
    }
    for (query Q : qs) {
        if (Q.u == cur) {
            if (des[Q.v] && top[Q.v] < Q.i) ans[Q.i] = -1;
            else ans[Q.i] = 0;
        } else if (Q.v == cur) {
            if (inc[Q.u] && pre[Q.u] < Q.i) ans[Q.i] = -1;
            else ans[Q.i] = 0;
        } else if (num[Q.u] != num[Q.v]) {
            if (des[Q.v] && inc[Q.u] && top[Q.v] < top[Q.u] && pre[Q.u] < Q.i) ans[Q.i] = -1;
            else ans[Q.i] = 0;
        } else ch[num[Q.u]].push_back(Q);
    }
    vis[cur] = 1;
    for (pii nxt : a[cur]) {
        if (vis[nxt.f]) continue;
        solve(nxt.f, ch[num[nxt.f]]);
    }
}

int find(int x) {
    return x == par[x] ? x : par[x] = find(par[x]);
}

bool merge(int x, int y) {
    for (int p : nodes[x]) nodes[y].push_back(p);
    nodes[x] = nodes[y];
    for (int p : nodes[x]) freq[p]++;
    return true;
}

int32_t main() {
    boost();

    vector<query> qs;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) par[i] = i, freq[i] = 1, nodes[i] = {i};
    for (int i = 1; i < n + q; i++) {
        cin >> c >> u;
        if (c != 'C') cin >> v;
        if (c == 'S') {
            a[u].push_back({v, i});
            a[v].push_back({u, i});
            if (n <= 4000) merge(u, v);
            ans[i] = -2;
        } else if (c == 'Q') {
            if (u == v) ans[i] = -1;
            else qs.push_back({1, u, v, i}); //v to u must be increasing
        } else {
            ans[i] = freq[u];
        }
    }
    solve(1, qs);
    for (int i = 1; i < n + q; i++) {
        if (ans[i] == -2) continue;
        if (ans[i] == -1) printf("yes\n");
        else if (ans[i] == 0) printf("no\n");
        else printf("%lld\n", ans[i]);
    }

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 79028 KB Output is correct
2 Correct 66 ms 81100 KB Output is correct
3 Correct 78 ms 95792 KB Output is correct
4 Correct 76 ms 83524 KB Output is correct
5 Correct 71 ms 84384 KB Output is correct
6 Correct 128 ms 146584 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 79028 KB Output is correct
2 Correct 66 ms 81100 KB Output is correct
3 Correct 78 ms 95792 KB Output is correct
4 Correct 76 ms 83524 KB Output is correct
5 Correct 71 ms 84384 KB Output is correct
6 Correct 128 ms 146584 KB Output is correct
7 Correct 61 ms 79544 KB Output is correct
8 Correct 65 ms 76588 KB Output is correct
9 Correct 76 ms 91528 KB Output is correct
10 Correct 66 ms 77396 KB Output is correct
11 Correct 66 ms 77892 KB Output is correct
12 Correct 123 ms 142768 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 77484 KB Output is correct
2 Correct 128 ms 96824 KB Output is correct
3 Correct 120 ms 96816 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 77484 KB Output is correct
2 Correct 128 ms 96824 KB Output is correct
3 Correct 120 ms 96816 KB Output is correct
4 Correct 57 ms 76988 KB Output is correct
5 Incorrect 125 ms 96392 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 80828 KB Output is correct
2 Correct 312 ms 148748 KB Output is correct
3 Correct 320 ms 149660 KB Output is correct
4 Correct 164 ms 117512 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 80828 KB Output is correct
2 Correct 312 ms 148748 KB Output is correct
3 Correct 320 ms 149660 KB Output is correct
4 Correct 164 ms 117512 KB Output is correct
5 Correct 59 ms 81368 KB Output is correct
6 Incorrect 291 ms 125620 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 79940 KB Output is correct
2 Correct 170 ms 113396 KB Output is correct
3 Correct 268 ms 139444 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 79940 KB Output is correct
2 Correct 170 ms 113396 KB Output is correct
3 Correct 268 ms 139444 KB Output is correct
4 Correct 60 ms 79804 KB Output is correct
5 Incorrect 152 ms 103300 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 80524 KB Output is correct
2 Correct 311 ms 148464 KB Output is correct
3 Correct 316 ms 149292 KB Output is correct
4 Correct 166 ms 117596 KB Output is correct
5 Correct 59 ms 80696 KB Output is correct
6 Correct 163 ms 113320 KB Output is correct
7 Correct 270 ms 139416 KB Output is correct
8 Correct 251 ms 104744 KB Output is correct
9 Correct 283 ms 129432 KB Output is correct
10 Correct 292 ms 129752 KB Output is correct
11 Correct 281 ms 115788 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 80524 KB Output is correct
2 Correct 311 ms 148464 KB Output is correct
3 Correct 316 ms 149292 KB Output is correct
4 Correct 166 ms 117596 KB Output is correct
5 Correct 59 ms 80696 KB Output is correct
6 Correct 163 ms 113320 KB Output is correct
7 Correct 270 ms 139416 KB Output is correct
8 Correct 251 ms 104744 KB Output is correct
9 Correct 283 ms 129432 KB Output is correct
10 Correct 292 ms 129752 KB Output is correct
11 Correct 281 ms 115788 KB Output is correct
12 Correct 59 ms 81336 KB Output is correct
13 Incorrect 302 ms 125532 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 78196 KB Output is correct
2 Correct 67 ms 80200 KB Output is correct
3 Correct 81 ms 94884 KB Output is correct
4 Correct 68 ms 82624 KB Output is correct
5 Correct 72 ms 83500 KB Output is correct
6 Correct 123 ms 145708 KB Output is correct
7 Correct 57 ms 76600 KB Output is correct
8 Correct 122 ms 96880 KB Output is correct
9 Correct 118 ms 96812 KB Output is correct
10 Correct 69 ms 81464 KB Output is correct
11 Correct 314 ms 150052 KB Output is correct
12 Correct 314 ms 150908 KB Output is correct
13 Correct 162 ms 117564 KB Output is correct
14 Correct 60 ms 80856 KB Output is correct
15 Correct 163 ms 113304 KB Output is correct
16 Correct 256 ms 139460 KB Output is correct
17 Correct 245 ms 104708 KB Output is correct
18 Correct 286 ms 129336 KB Output is correct
19 Correct 315 ms 129748 KB Output is correct
20 Correct 269 ms 115636 KB Output is correct
21 Correct 143 ms 100216 KB Output is correct
22 Correct 142 ms 102348 KB Output is correct
23 Correct 218 ms 117056 KB Output is correct
24 Correct 215 ms 116520 KB Output is correct
25 Correct 351 ms 132312 KB Output is correct
26 Correct 280 ms 118056 KB Output is correct
27 Correct 258 ms 117380 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 78196 KB Output is correct
2 Correct 67 ms 80200 KB Output is correct
3 Correct 81 ms 94884 KB Output is correct
4 Correct 68 ms 82624 KB Output is correct
5 Correct 72 ms 83500 KB Output is correct
6 Correct 123 ms 145708 KB Output is correct
7 Correct 57 ms 76600 KB Output is correct
8 Correct 122 ms 96880 KB Output is correct
9 Correct 118 ms 96812 KB Output is correct
10 Correct 69 ms 81464 KB Output is correct
11 Correct 314 ms 150052 KB Output is correct
12 Correct 314 ms 150908 KB Output is correct
13 Correct 162 ms 117564 KB Output is correct
14 Correct 60 ms 80856 KB Output is correct
15 Correct 163 ms 113304 KB Output is correct
16 Correct 256 ms 139460 KB Output is correct
17 Correct 245 ms 104708 KB Output is correct
18 Correct 286 ms 129336 KB Output is correct
19 Correct 315 ms 129748 KB Output is correct
20 Correct 269 ms 115636 KB Output is correct
21 Correct 143 ms 100216 KB Output is correct
22 Correct 142 ms 102348 KB Output is correct
23 Correct 218 ms 117056 KB Output is correct
24 Correct 215 ms 116520 KB Output is correct
25 Correct 351 ms 132312 KB Output is correct
26 Correct 280 ms 118056 KB Output is correct
27 Correct 258 ms 117380 KB Output is correct
28 Correct 59 ms 79544 KB Output is correct
29 Correct 67 ms 76508 KB Output is correct
30 Correct 80 ms 91508 KB Output is correct
31 Correct 69 ms 77292 KB Output is correct
32 Correct 66 ms 77876 KB Output is correct
33 Correct 123 ms 142784 KB Output is correct
34 Correct 57 ms 77020 KB Output is correct
35 Incorrect 131 ms 96440 KB Extra information in the output file
36 Halted 0 ms 0 KB -