oj.uz

Submission #531952

# Submission time Handle Problem Language Result Execution time Memory
531952 2022-03-02T01:24:41 Z 4fecta Inside information (BOI21_servers) C++17
5 / 100
 599 ms 524292 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});
            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 63 ms 78448 KB Output is correct
2 Correct 70 ms 80480 KB Output is correct
3 Correct 82 ms 95136 KB Output is correct
4 Correct 73 ms 82916 KB Output is correct
5 Correct 73 ms 83820 KB Output is correct
6 Correct 129 ms 145908 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 78448 KB Output is correct
2 Correct 70 ms 80480 KB Output is correct
3 Correct 82 ms 95136 KB Output is correct
4 Correct 73 ms 82916 KB Output is correct
5 Correct 73 ms 83820 KB Output is correct
6 Correct 129 ms 145908 KB Output is correct
7 Correct 68 ms 79092 KB Output is correct
8 Correct 67 ms 76596 KB Output is correct
9 Correct 78 ms 91524 KB Output is correct
10 Correct 69 ms 77352 KB Output is correct
11 Correct 67 ms 77948 KB Output is correct
12 Correct 126 ms 142708 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 76808 KB Output is correct
2 Runtime error 518 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 76808 KB Output is correct
2 Runtime error 518 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 81264 KB Output is correct
2 Correct 454 ms 153272 KB Output is correct
3 Correct 430 ms 153896 KB Output is correct
4 Runtime error 321 ms 524292 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 81264 KB Output is correct
2 Correct 454 ms 153272 KB Output is correct
3 Correct 430 ms 153896 KB Output is correct
4 Runtime error 321 ms 524292 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 80728 KB Output is correct
2 Runtime error 599 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 80728 KB Output is correct
2 Runtime error 599 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 81456 KB Output is correct
2 Correct 475 ms 153388 KB Output is correct
3 Correct 439 ms 154048 KB Output is correct
4 Runtime error 315 ms 524292 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 81456 KB Output is correct
2 Correct 475 ms 153388 KB Output is correct
3 Correct 439 ms 154048 KB Output is correct
4 Runtime error 315 ms 524292 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 79108 KB Output is correct
2 Correct 72 ms 81124 KB Output is correct
3 Correct 85 ms 95808 KB Output is correct
4 Correct 74 ms 83560 KB Output is correct
5 Correct 77 ms 84380 KB Output is correct
6 Correct 133 ms 146532 KB Output is correct
7 Correct 64 ms 77416 KB Output is correct
8 Runtime error 504 ms 524292 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 79108 KB Output is correct
2 Correct 72 ms 81124 KB Output is correct
3 Correct 85 ms 95808 KB Output is correct
4 Correct 74 ms 83560 KB Output is correct
5 Correct 77 ms 84380 KB Output is correct
6 Correct 133 ms 146532 KB Output is correct
7 Correct 64 ms 77416 KB Output is correct
8 Runtime error 504 ms 524292 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -