oj.uz

Submission #1040697

# Submission time Handle Problem Language Result Execution time Memory
1040697 2024-08-01T08:32:38 Z Plurm Inside information (BOI21_servers) C++11
100 / 100
 3412 ms 232788 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 = 1024;
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 51 ms 199112 KB Output is correct
2 Correct 68 ms 199404 KB Output is correct
3 Correct 59 ms 199648 KB Output is correct
4 Correct 57 ms 199640 KB Output is correct
5 Correct 64 ms 199952 KB Output is correct
6 Correct 62 ms 199944 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 199112 KB Output is correct
2 Correct 68 ms 199404 KB Output is correct
3 Correct 59 ms 199648 KB Output is correct
4 Correct 57 ms 199640 KB Output is correct
5 Correct 64 ms 199952 KB Output is correct
6 Correct 62 ms 199944 KB Output is correct
7 Correct 70 ms 199100 KB Output is correct
8 Correct 786 ms 199484 KB Output is correct
9 Correct 433 ms 199688 KB Output is correct
10 Correct 674 ms 199648 KB Output is correct
11 Correct 1000 ms 199940 KB Output is correct
12 Correct 389 ms 199908 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 199056 KB Output is correct
2 Correct 120 ms 232700 KB Output is correct
3 Correct 146 ms 232740 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 199056 KB Output is correct
2 Correct 120 ms 232700 KB Output is correct
3 Correct 146 ms 232740 KB Output is correct
4 Correct 65 ms 199116 KB Output is correct
5 Correct 874 ms 230804 KB Output is correct
6 Correct 1074 ms 231172 KB Output is correct
7 Correct 1258 ms 231104 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 199344 KB Output is correct
2 Correct 144 ms 231424 KB Output is correct
3 Correct 159 ms 231604 KB Output is correct
4 Correct 134 ms 232704 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 199344 KB Output is correct
2 Correct 144 ms 231424 KB Output is correct
3 Correct 159 ms 231604 KB Output is correct
4 Correct 134 ms 232704 KB Output is correct
5 Correct 79 ms 199112 KB Output is correct
6 Correct 2904 ms 229472 KB Output is correct
7 Correct 613 ms 230952 KB Output is correct
8 Correct 3358 ms 229340 KB Output is correct
9 Correct 3412 ms 229476 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 199104 KB Output is correct
2 Correct 105 ms 221012 KB Output is correct
3 Correct 138 ms 220416 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 199104 KB Output is correct
2 Correct 105 ms 221012 KB Output is correct
3 Correct 138 ms 220416 KB Output is correct
4 Correct 56 ms 199192 KB Output is correct
5 Correct 759 ms 219084 KB Output is correct
6 Correct 1625 ms 220776 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 199104 KB Output is correct
2 Correct 144 ms 231428 KB Output is correct
3 Correct 139 ms 231424 KB Output is correct
4 Correct 103 ms 232708 KB Output is correct
5 Correct 52 ms 199112 KB Output is correct
6 Correct 109 ms 220932 KB Output is correct
7 Correct 134 ms 220528 KB Output is correct
8 Correct 138 ms 220928 KB Output is correct
9 Correct 132 ms 220932 KB Output is correct
10 Correct 127 ms 225532 KB Output is correct
11 Correct 118 ms 224764 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 199104 KB Output is correct
2 Correct 144 ms 231428 KB Output is correct
3 Correct 139 ms 231424 KB Output is correct
4 Correct 103 ms 232708 KB Output is correct
5 Correct 52 ms 199112 KB Output is correct
6 Correct 109 ms 220932 KB Output is correct
7 Correct 134 ms 220528 KB Output is correct
8 Correct 138 ms 220928 KB Output is correct
9 Correct 132 ms 220932 KB Output is correct
10 Correct 127 ms 225532 KB Output is correct
11 Correct 118 ms 224764 KB Output is correct
12 Correct 55 ms 199112 KB Output is correct
13 Correct 2751 ms 229608 KB Output is correct
14 Correct 635 ms 230816 KB Output is correct
15 Correct 3328 ms 229364 KB Output is correct
16 Correct 3201 ms 229380 KB Output is correct
17 Correct 53 ms 199116 KB Output is correct
18 Correct 764 ms 219132 KB Output is correct
19 Correct 1591 ms 220708 KB Output is correct
20 Correct 1987 ms 219004 KB Output is correct
21 Correct 2522 ms 218880 KB Output is correct
22 Correct 1935 ms 222724 KB Output is correct
23 Correct 1215 ms 225044 KB Output is correct
24 Correct 477 ms 225280 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 199108 KB Output is correct
2 Correct 59 ms 199528 KB Output is correct
3 Correct 58 ms 199548 KB Output is correct
4 Correct 59 ms 199688 KB Output is correct
5 Correct 58 ms 200016 KB Output is correct
6 Correct 57 ms 199944 KB Output is correct
7 Correct 51 ms 199120 KB Output is correct
8 Correct 142 ms 232760 KB Output is correct
9 Correct 111 ms 232788 KB Output is correct
10 Correct 49 ms 199108 KB Output is correct
11 Correct 132 ms 231680 KB Output is correct
12 Correct 138 ms 231420 KB Output is correct
13 Correct 106 ms 232624 KB Output is correct
14 Correct 52 ms 199112 KB Output is correct
15 Correct 108 ms 221056 KB Output is correct
16 Correct 126 ms 220416 KB Output is correct
17 Correct 125 ms 220924 KB Output is correct
18 Correct 129 ms 220924 KB Output is correct
19 Correct 122 ms 225524 KB Output is correct
20 Correct 133 ms 224716 KB Output is correct
21 Correct 115 ms 225380 KB Output is correct
22 Correct 120 ms 225536 KB Output is correct
23 Correct 131 ms 221952 KB Output is correct
24 Correct 139 ms 222204 KB Output is correct
25 Correct 139 ms 227588 KB Output is correct
26 Correct 121 ms 221152 KB Output is correct
27 Correct 111 ms 221436 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 199108 KB Output is correct
2 Correct 59 ms 199528 KB Output is correct
3 Correct 58 ms 199548 KB Output is correct
4 Correct 59 ms 199688 KB Output is correct
5 Correct 58 ms 200016 KB Output is correct
6 Correct 57 ms 199944 KB Output is correct
7 Correct 51 ms 199120 KB Output is correct
8 Correct 142 ms 232760 KB Output is correct
9 Correct 111 ms 232788 KB Output is correct
10 Correct 49 ms 199108 KB Output is correct
11 Correct 132 ms 231680 KB Output is correct
12 Correct 138 ms 231420 KB Output is correct
13 Correct 106 ms 232624 KB Output is correct
14 Correct 52 ms 199112 KB Output is correct
15 Correct 108 ms 221056 KB Output is correct
16 Correct 126 ms 220416 KB Output is correct
17 Correct 125 ms 220924 KB Output is correct
18 Correct 129 ms 220924 KB Output is correct
19 Correct 122 ms 225524 KB Output is correct
20 Correct 133 ms 224716 KB Output is correct
21 Correct 115 ms 225380 KB Output is correct
22 Correct 120 ms 225536 KB Output is correct
23 Correct 131 ms 221952 KB Output is correct
24 Correct 139 ms 222204 KB Output is correct
25 Correct 139 ms 227588 KB Output is correct
26 Correct 121 ms 221152 KB Output is correct
27 Correct 111 ms 221436 KB Output is correct
28 Correct 55 ms 198956 KB Output is correct
29 Correct 659 ms 199384 KB Output is correct
30 Correct 411 ms 199560 KB Output is correct
31 Correct 642 ms 199584 KB Output is correct
32 Correct 889 ms 199944 KB Output is correct
33 Correct 371 ms 199944 KB Output is correct
34 Correct 53 ms 199212 KB Output is correct
35 Correct 717 ms 230912 KB Output is correct
36 Correct 974 ms 231168 KB Output is correct
37 Correct 1083 ms 231052 KB Output is correct
38 Correct 55 ms 199116 KB Output is correct
39 Correct 2473 ms 229636 KB Output is correct
40 Correct 643 ms 230844 KB Output is correct
41 Correct 3272 ms 229460 KB Output is correct
42 Correct 3238 ms 229892 KB Output is correct
43 Correct 54 ms 199104 KB Output is correct
44 Correct 774 ms 219160 KB Output is correct
45 Correct 1671 ms 220624 KB Output is correct
46 Correct 1996 ms 219144 KB Output is correct
47 Correct 2494 ms 218936 KB Output is correct
48 Correct 1899 ms 222720 KB Output is correct
49 Correct 1218 ms 225240 KB Output is correct
50 Correct 513 ms 225356 KB Output is correct
51 Correct 1130 ms 229376 KB Output is correct
52 Correct 914 ms 226308 KB Output is correct
53 Correct 1153 ms 228080 KB Output is correct
54 Correct 936 ms 226464 KB Output is correct
55 Correct 1335 ms 228352 KB Output is correct
56 Correct 1812 ms 220044 KB Output is correct
57 Correct 2133 ms 226816 KB Output is correct
58 Correct 1631 ms 221188 KB Output is correct
59 Correct 279 ms 221572 KB Output is correct