oj.uz

Submission #1040690

# Submission time Handle Problem Language Result Execution time Memory
1040690 2024-08-01T08:30:15 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 232836 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> g[1 << 19];
vector<int> rg[1 << 19];
int st[1 << 19];
int dep[1 << 19];
int ddep[1 << 19];
int t;
int ett[1048576];
int rev[1048576];
void dfs(int u, int p = 0, int d = 0){
    t++;
    ddep[u] = d;
    ett[t] = dep[u] = dep[p]+1;
    st[u] = t;
    rev[t] = u;
    for(int v : g[u]){
        if(v == p) continue;
        dfs(v, u, d+1);
        t++;
        ett[t] = dep[u];
        rev[t] = u;
    }
    for(int v : rg[u]){
        if(v == p) continue;
        dfs(v, u, d-1);
        t++;
        ett[t] = dep[u];
        rev[t] = u;
    }
}
pair<int, int> sparse[21][1048576];
void build(){
    for(int i = 0; i < 1048576; i++) sparse[0][i] = {ett[i], rev[i]};
    for(int i = 1; i < 21; i++){
        for(int j = 0; j + (1 << i) < 1048576; j++){
            sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j+(1<<(i-1))]);
        }
    }
}
inline bool search(const int& a, const int& d){
    int l, r;
    tie(l, r) = minmax(st[a], st[d]);
    int lg = 31 - __builtin_clz(r-l+1);
    return dep[a] + dep[d] - 2*dep[min(sparse[lg][l], sparse[lg][r-(1<<lg)+1]).second] == ddep[d] - ddep[a];
}
tuple<int,int,int> buffer[1 << 19];
int bsz;
const int THRESH = 900;
int qs[1 << 19];
int evp[1 << 19];
int update(int u, int p = 0, int d = 0){
    for(int v : rg[u]){
        if(v == p) continue;
        d += update(v, u, 0);
    }
    d += evp[u];
    qs[u] += d;
    for(int v : g[u]){
        if(v == p) continue;
        update(v, u, d);
    }
    return d;
}
int count(int d){
    if(bsz >= THRESH){
        for(int i = 0; i < bsz; i++){
            evp[get<0>(buffer[i])]--;
            evp[get<1>(buffer[i])]--;
            evp[get<2>(buffer[i])] += 2;
        }
        update(1);
        for(int i = 0; i < bsz; i++){
            evp[get<0>(buffer[i])]++;
            evp[get<1>(buffer[i])]++;
            evp[get<2>(buffer[i])] -= 2;
        }
        bsz = 0;
    }
    int ret = qs[d];
    for(int i = 0; i < bsz; i++){
        if(search(get<0>(buffer[i]), d) || search(get<1>(buffer[i]), d)){
            ret++;
        }else if(search(get<2>(buffer[i]), d)){
            ret += 2;
        }
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    k += n-1;
    vector<tuple<int,int,int>> cmds;
    vector<int> ids(n+1);
    for(int i = 1; i <= n; i++){
        ids[i] = i;
    }
    int last = n;
    for(int i = 0; i < k; i++){
        string cmd;
        cin >> cmd;
        int a, b, d;
        switch(cmd[0]){
            case 'S':
                cin >> a >> b;
                last++;
                g[last].push_back(ids[a]);
                rg[ids[a]].push_back(last);
                g[last].push_back(ids[b]);
                rg[ids[b]].push_back(last);
                ids[a] = ids[b] = last;
                cmds.push_back({0, a, b});
                break;
            case 'Q':
                cin >> a >> d;
                cmds.push_back({1, a, d});
                break;
            case 'C':
                cin >> d;
                cmds.push_back({2, d, 0});
                break;
        }
    }
    dfs(1);
    build();
    for(int i = 1; i <= n; i++){
        ids[i] = i;
        qs[i]++;
    }
    last = n;
    for(int i = 0; i < k; i++){
        int a, b, d;
        switch(get<0>(cmds[i])){
            case 0:
                a = get<1>(cmds[i]);
                b = get<2>(cmds[i]);
                last++;
                buffer[bsz++] = {ids[a], ids[b], last};
                ids[a] = ids[b] = last;
                break;
            case 1:
                a = get<1>(cmds[i]);
                d = get<2>(cmds[i]);
                if(search(ids[a], d)) cout << "yes\n";
                else cout << "no\n";
                break;
            case 2:
                d = get<1>(cmds[i]);
                cout << count(d) << "\n";
                break;
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 199112 KB Output is correct
2 Correct 64 ms 199432 KB Output is correct
3 Correct 59 ms 199736 KB Output is correct
4 Correct 58 ms 199652 KB Output is correct
5 Correct 76 ms 199864 KB Output is correct
6 Correct 60 ms 199836 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 199112 KB Output is correct
2 Correct 64 ms 199432 KB Output is correct
3 Correct 59 ms 199736 KB Output is correct
4 Correct 58 ms 199652 KB Output is correct
5 Correct 76 ms 199864 KB Output is correct
6 Correct 60 ms 199836 KB Output is correct
7 Correct 57 ms 199076 KB Output is correct
8 Correct 579 ms 199328 KB Output is correct
9 Correct 354 ms 199676 KB Output is correct
10 Correct 580 ms 199584 KB Output is correct
11 Correct 412 ms 199972 KB Output is correct
12 Correct 262 ms 199972 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 199080 KB Output is correct
2 Correct 138 ms 232836 KB Output is correct
3 Correct 120 ms 232768 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 199080 KB Output is correct
2 Correct 138 ms 232836 KB Output is correct
3 Correct 120 ms 232768 KB Output is correct
4 Correct 60 ms 199312 KB Output is correct
5 Correct 890 ms 230852 KB Output is correct
6 Correct 1086 ms 231228 KB Output is correct
7 Correct 1199 ms 231068 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 199108 KB Output is correct
2 Correct 140 ms 231584 KB Output is correct
3 Correct 138 ms 231376 KB Output is correct
4 Correct 106 ms 232812 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 199108 KB Output is correct
2 Correct 140 ms 231584 KB Output is correct
3 Correct 138 ms 231376 KB Output is correct
4 Correct 106 ms 232812 KB Output is correct
5 Correct 63 ms 199112 KB Output is correct
6 Execution timed out 3523 ms 229484 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 199112 KB Output is correct
2 Correct 122 ms 221112 KB Output is correct
3 Correct 147 ms 220416 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 199112 KB Output is correct
2 Correct 122 ms 221112 KB Output is correct
3 Correct 147 ms 220416 KB Output is correct
4 Correct 60 ms 199108 KB Output is correct
5 Correct 773 ms 219340 KB Output is correct
6 Correct 1809 ms 220660 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 79 ms 199136 KB Output is correct
2 Correct 138 ms 231560 KB Output is correct
3 Correct 137 ms 231428 KB Output is correct
4 Correct 121 ms 232708 KB Output is correct
5 Correct 57 ms 199112 KB Output is correct
6 Correct 102 ms 220964 KB Output is correct
7 Correct 155 ms 220624 KB Output is correct
8 Correct 156 ms 220952 KB Output is correct
9 Correct 154 ms 220784 KB Output is correct
10 Correct 119 ms 225692 KB Output is correct
11 Correct 152 ms 224768 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 79 ms 199136 KB Output is correct
2 Correct 138 ms 231560 KB Output is correct
3 Correct 137 ms 231428 KB Output is correct
4 Correct 121 ms 232708 KB Output is correct
5 Correct 57 ms 199112 KB Output is correct
6 Correct 102 ms 220964 KB Output is correct
7 Correct 155 ms 220624 KB Output is correct
8 Correct 156 ms 220952 KB Output is correct
9 Correct 154 ms 220784 KB Output is correct
10 Correct 119 ms 225692 KB Output is correct
11 Correct 152 ms 224768 KB Output is correct
12 Correct 58 ms 199112 KB Output is correct
13 Correct 3438 ms 229780 KB Output is correct
14 Correct 719 ms 230904 KB Output is correct
15 Execution timed out 3565 ms 229604 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 198964 KB Output is correct
2 Correct 59 ms 199528 KB Output is correct
3 Correct 56 ms 199604 KB Output is correct
4 Correct 60 ms 199596 KB Output is correct
5 Correct 58 ms 199796 KB Output is correct
6 Correct 75 ms 199940 KB Output is correct
7 Correct 57 ms 199112 KB Output is correct
8 Correct 110 ms 232720 KB Output is correct
9 Correct 158 ms 232704 KB Output is correct
10 Correct 66 ms 199016 KB Output is correct
11 Correct 164 ms 231460 KB Output is correct
12 Correct 150 ms 231440 KB Output is correct
13 Correct 120 ms 232688 KB Output is correct
14 Correct 50 ms 199092 KB Output is correct
15 Correct 131 ms 220928 KB Output is correct
16 Correct 152 ms 220716 KB Output is correct
17 Correct 136 ms 220888 KB Output is correct
18 Correct 133 ms 220832 KB Output is correct
19 Correct 117 ms 225540 KB Output is correct
20 Correct 126 ms 224832 KB Output is correct
21 Correct 114 ms 225284 KB Output is correct
22 Correct 148 ms 225536 KB Output is correct
23 Correct 171 ms 221952 KB Output is correct
24 Correct 142 ms 222064 KB Output is correct
25 Correct 143 ms 227484 KB Output is correct
26 Correct 126 ms 221332 KB Output is correct
27 Correct 128 ms 221732 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 198964 KB Output is correct
2 Correct 59 ms 199528 KB Output is correct
3 Correct 56 ms 199604 KB Output is correct
4 Correct 60 ms 199596 KB Output is correct
5 Correct 58 ms 199796 KB Output is correct
6 Correct 75 ms 199940 KB Output is correct
7 Correct 57 ms 199112 KB Output is correct
8 Correct 110 ms 232720 KB Output is correct
9 Correct 158 ms 232704 KB Output is correct
10 Correct 66 ms 199016 KB Output is correct
11 Correct 164 ms 231460 KB Output is correct
12 Correct 150 ms 231440 KB Output is correct
13 Correct 120 ms 232688 KB Output is correct
14 Correct 50 ms 199092 KB Output is correct
15 Correct 131 ms 220928 KB Output is correct
16 Correct 152 ms 220716 KB Output is correct
17 Correct 136 ms 220888 KB Output is correct
18 Correct 133 ms 220832 KB Output is correct
19 Correct 117 ms 225540 KB Output is correct
20 Correct 126 ms 224832 KB Output is correct
21 Correct 114 ms 225284 KB Output is correct
22 Correct 148 ms 225536 KB Output is correct
23 Correct 171 ms 221952 KB Output is correct
24 Correct 142 ms 222064 KB Output is correct
25 Correct 143 ms 227484 KB Output is correct
26 Correct 126 ms 221332 KB Output is correct
27 Correct 128 ms 221732 KB Output is correct
28 Correct 58 ms 199108 KB Output is correct
29 Correct 601 ms 199492 KB Output is correct
30 Correct 375 ms 199632 KB Output is correct
31 Correct 576 ms 199556 KB Output is correct
32 Correct 420 ms 199840 KB Output is correct
33 Correct 239 ms 199916 KB Output is correct
34 Correct 55 ms 199224 KB Output is correct
35 Correct 978 ms 230820 KB Output is correct
36 Correct 1154 ms 231172 KB Output is correct
37 Correct 1362 ms 231172 KB Output is correct
38 Correct 60 ms 199076 KB Output is correct
39 Execution timed out 3575 ms 229556 KB Time limit exceeded
40 Halted 0 ms 0 KB -