oj.uz

Submission #531932

# Submission time Handle Problem Language Result Execution time Memory
531932 2022-03-02T00:10:47 Z 4fecta Inside information (BOI21_servers) C++17
50 / 100
 358 ms 141224 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];
char c;
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]]);
    }
}

int32_t main() {
    boost();

    vector<query> qs;
    cin >> n >> q;
    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});
            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] = 1;
        }
    }
    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 54 ms 72472 KB Output is correct
2 Correct 65 ms 74128 KB Output is correct
3 Correct 68 ms 80140 KB Output is correct
4 Correct 64 ms 76592 KB Output is correct
5 Correct 65 ms 77544 KB Output is correct
6 Correct 70 ms 71140 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 72472 KB Output is correct
2 Correct 65 ms 74128 KB Output is correct
3 Correct 68 ms 80140 KB Output is correct
4 Correct 64 ms 76592 KB Output is correct
5 Correct 65 ms 77544 KB Output is correct
6 Correct 70 ms 71140 KB Output is correct
7 Incorrect 58 ms 73024 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 70868 KB Output is correct
2 Correct 121 ms 86744 KB Output is correct
3 Correct 132 ms 86780 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 70868 KB Output is correct
2 Correct 121 ms 86744 KB Output is correct
3 Correct 132 ms 86780 KB Output is correct
4 Incorrect 58 ms 71484 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 74916 KB Output is correct
2 Correct 313 ms 140468 KB Output is correct
3 Correct 353 ms 141224 KB Output is correct
4 Correct 174 ms 107868 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 74916 KB Output is correct
2 Correct 313 ms 140468 KB Output is correct
3 Correct 353 ms 141224 KB Output is correct
4 Correct 174 ms 107868 KB Output is correct
5 Incorrect 67 ms 75764 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 74168 KB Output is correct
2 Correct 168 ms 103640 KB Output is correct
3 Correct 293 ms 129784 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 74168 KB Output is correct
2 Correct 168 ms 103640 KB Output is correct
3 Correct 293 ms 129784 KB Output is correct
4 Incorrect 54 ms 74236 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 75 ms 74928 KB Output is correct
2 Correct 326 ms 140420 KB Output is correct
3 Correct 343 ms 141184 KB Output is correct
4 Correct 161 ms 107936 KB Output is correct
5 Correct 71 ms 75100 KB Output is correct
6 Correct 162 ms 103596 KB Output is correct
7 Correct 248 ms 129700 KB Output is correct
8 Correct 251 ms 95108 KB Output is correct
9 Correct 277 ms 119712 KB Output is correct
10 Correct 287 ms 120104 KB Output is correct
11 Correct 301 ms 106192 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 75 ms 74928 KB Output is correct
2 Correct 326 ms 140420 KB Output is correct
3 Correct 343 ms 141184 KB Output is correct
4 Correct 161 ms 107936 KB Output is correct
5 Correct 71 ms 75100 KB Output is correct
6 Correct 162 ms 103596 KB Output is correct
7 Correct 248 ms 129700 KB Output is correct
8 Correct 251 ms 95108 KB Output is correct
9 Correct 277 ms 119712 KB Output is correct
10 Correct 287 ms 120104 KB Output is correct
11 Correct 301 ms 106192 KB Output is correct
12 Incorrect 58 ms 75672 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 72460 KB Output is correct
2 Correct 62 ms 74156 KB Output is correct
3 Correct 74 ms 80088 KB Output is correct
4 Correct 67 ms 76568 KB Output is correct
5 Correct 68 ms 77608 KB Output is correct
6 Correct 62 ms 71216 KB Output is correct
7 Correct 56 ms 70860 KB Output is correct
8 Correct 118 ms 86740 KB Output is correct
9 Correct 116 ms 86756 KB Output is correct
10 Correct 61 ms 75736 KB Output is correct
11 Correct 313 ms 140404 KB Output is correct
12 Correct 310 ms 141224 KB Output is correct
13 Correct 172 ms 107864 KB Output is correct
14 Correct 59 ms 75060 KB Output is correct
15 Correct 152 ms 103588 KB Output is correct
16 Correct 302 ms 129784 KB Output is correct
17 Correct 242 ms 95008 KB Output is correct
18 Correct 290 ms 119628 KB Output is correct
19 Correct 303 ms 120092 KB Output is correct
20 Correct 262 ms 105968 KB Output is correct
21 Correct 135 ms 90532 KB Output is correct
22 Correct 138 ms 92820 KB Output is correct
23 Correct 205 ms 107360 KB Output is correct
24 Correct 214 ms 106880 KB Output is correct
25 Correct 358 ms 122504 KB Output is correct
26 Correct 309 ms 108732 KB Output is correct
27 Correct 265 ms 107696 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 72460 KB Output is correct
2 Correct 62 ms 74156 KB Output is correct
3 Correct 74 ms 80088 KB Output is correct
4 Correct 67 ms 76568 KB Output is correct
5 Correct 68 ms 77608 KB Output is correct
6 Correct 62 ms 71216 KB Output is correct
7 Correct 56 ms 70860 KB Output is correct
8 Correct 118 ms 86740 KB Output is correct
9 Correct 116 ms 86756 KB Output is correct
10 Correct 61 ms 75736 KB Output is correct
11 Correct 313 ms 140404 KB Output is correct
12 Correct 310 ms 141224 KB Output is correct
13 Correct 172 ms 107864 KB Output is correct
14 Correct 59 ms 75060 KB Output is correct
15 Correct 152 ms 103588 KB Output is correct
16 Correct 302 ms 129784 KB Output is correct
17 Correct 242 ms 95008 KB Output is correct
18 Correct 290 ms 119628 KB Output is correct
19 Correct 303 ms 120092 KB Output is correct
20 Correct 262 ms 105968 KB Output is correct
21 Correct 135 ms 90532 KB Output is correct
22 Correct 138 ms 92820 KB Output is correct
23 Correct 205 ms 107360 KB Output is correct
24 Correct 214 ms 106880 KB Output is correct
25 Correct 358 ms 122504 KB Output is correct
26 Correct 309 ms 108732 KB Output is correct
27 Correct 265 ms 107696 KB Output is correct
28 Incorrect 61 ms 73868 KB Extra information in the output file
29 Halted 0 ms 0 KB -