oj.uz

Submission #1040685

# Submission time Handle Problem Language Result Execution time Memory
1040685 2024-08-01T08:28:33 Z Plurm Inside information (BOI21_servers) C++11
82.5 / 100
 3500 ms 232880 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 = 1000;
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 53 ms 199104 KB Output is correct
2 Correct 61 ms 199520 KB Output is correct
3 Correct 57 ms 199680 KB Output is correct
4 Correct 63 ms 199708 KB Output is correct
5 Correct 62 ms 199856 KB Output is correct
6 Correct 60 ms 199940 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 199104 KB Output is correct
2 Correct 61 ms 199520 KB Output is correct
3 Correct 57 ms 199680 KB Output is correct
4 Correct 63 ms 199708 KB Output is correct
5 Correct 62 ms 199856 KB Output is correct
6 Correct 60 ms 199940 KB Output is correct
7 Correct 56 ms 199108 KB Output is correct
8 Correct 670 ms 199416 KB Output is correct
9 Correct 378 ms 199684 KB Output is correct
10 Correct 639 ms 199652 KB Output is correct
11 Correct 976 ms 199776 KB Output is correct
12 Correct 383 ms 200004 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 199112 KB Output is correct
2 Correct 109 ms 232704 KB Output is correct
3 Correct 115 ms 232704 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 199112 KB Output is correct
2 Correct 109 ms 232704 KB Output is correct
3 Correct 115 ms 232704 KB Output is correct
4 Correct 57 ms 199112 KB Output is correct
5 Correct 713 ms 230872 KB Output is correct
6 Correct 1103 ms 231180 KB Output is correct
7 Correct 1219 ms 230904 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 199108 KB Output is correct
2 Correct 146 ms 231564 KB Output is correct
3 Correct 158 ms 231420 KB Output is correct
4 Correct 107 ms 232696 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 199108 KB Output is correct
2 Correct 146 ms 231564 KB Output is correct
3 Correct 158 ms 231420 KB Output is correct
4 Correct 107 ms 232696 KB Output is correct
5 Correct 54 ms 199112 KB Output is correct
6 Correct 2722 ms 229648 KB Output is correct
7 Correct 628 ms 230848 KB Output is correct
8 Correct 3267 ms 229568 KB Output is correct
9 Correct 3215 ms 229372 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 199108 KB Output is correct
2 Correct 102 ms 221120 KB Output is correct
3 Correct 128 ms 220492 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 199108 KB Output is correct
2 Correct 102 ms 221120 KB Output is correct
3 Correct 128 ms 220492 KB Output is correct
4 Correct 54 ms 199108 KB Output is correct
5 Correct 758 ms 219132 KB Output is correct
6 Correct 1587 ms 220620 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 199108 KB Output is correct
2 Correct 145 ms 231632 KB Output is correct
3 Correct 133 ms 231424 KB Output is correct
4 Correct 103 ms 232704 KB Output is correct
5 Correct 52 ms 199112 KB Output is correct
6 Correct 110 ms 220908 KB Output is correct
7 Correct 137 ms 220832 KB Output is correct
8 Correct 136 ms 220928 KB Output is correct
9 Correct 132 ms 220820 KB Output is correct
10 Correct 121 ms 225796 KB Output is correct
11 Correct 116 ms 224824 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 199108 KB Output is correct
2 Correct 145 ms 231632 KB Output is correct
3 Correct 133 ms 231424 KB Output is correct
4 Correct 103 ms 232704 KB Output is correct
5 Correct 52 ms 199112 KB Output is correct
6 Correct 110 ms 220908 KB Output is correct
7 Correct 137 ms 220832 KB Output is correct
8 Correct 136 ms 220928 KB Output is correct
9 Correct 132 ms 220820 KB Output is correct
10 Correct 121 ms 225796 KB Output is correct
11 Correct 116 ms 224824 KB Output is correct
12 Correct 64 ms 199104 KB Output is correct
13 Correct 2522 ms 229640 KB Output is correct
14 Correct 641 ms 231076 KB Output is correct
15 Correct 3215 ms 229644 KB Output is correct
16 Correct 3129 ms 229380 KB Output is correct
17 Correct 66 ms 199116 KB Output is correct
18 Correct 757 ms 219136 KB Output is correct
19 Correct 1568 ms 220668 KB Output is correct
20 Correct 2753 ms 219268 KB Output is correct
21 Correct 2333 ms 219032 KB Output is correct
22 Correct 1880 ms 222704 KB Output is correct
23 Correct 1191 ms 224756 KB Output is correct
24 Correct 592 ms 225280 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 198992 KB Output is correct
2 Correct 58 ms 199392 KB Output is correct
3 Correct 68 ms 199684 KB Output is correct
4 Correct 60 ms 199640 KB Output is correct
5 Correct 69 ms 199944 KB Output is correct
6 Correct 55 ms 199808 KB Output is correct
7 Correct 54 ms 199108 KB Output is correct
8 Correct 127 ms 232704 KB Output is correct
9 Correct 134 ms 232704 KB Output is correct
10 Correct 52 ms 199108 KB Output is correct
11 Correct 146 ms 231440 KB Output is correct
12 Correct 153 ms 231424 KB Output is correct
13 Correct 115 ms 232880 KB Output is correct
14 Correct 53 ms 199152 KB Output is correct
15 Correct 106 ms 220960 KB Output is correct
16 Correct 139 ms 220420 KB Output is correct
17 Correct 133 ms 220836 KB Output is correct
18 Correct 152 ms 221004 KB Output is correct
19 Correct 133 ms 225628 KB Output is correct
20 Correct 130 ms 224772 KB Output is correct
21 Correct 120 ms 225280 KB Output is correct
22 Correct 119 ms 225536 KB Output is correct
23 Correct 154 ms 221956 KB Output is correct
24 Correct 143 ms 222212 KB Output is correct
25 Correct 137 ms 227836 KB Output is correct
26 Correct 153 ms 221180 KB Output is correct
27 Correct 113 ms 221440 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 198992 KB Output is correct
2 Correct 58 ms 199392 KB Output is correct
3 Correct 68 ms 199684 KB Output is correct
4 Correct 60 ms 199640 KB Output is correct
5 Correct 69 ms 199944 KB Output is correct
6 Correct 55 ms 199808 KB Output is correct
7 Correct 54 ms 199108 KB Output is correct
8 Correct 127 ms 232704 KB Output is correct
9 Correct 134 ms 232704 KB Output is correct
10 Correct 52 ms 199108 KB Output is correct
11 Correct 146 ms 231440 KB Output is correct
12 Correct 153 ms 231424 KB Output is correct
13 Correct 115 ms 232880 KB Output is correct
14 Correct 53 ms 199152 KB Output is correct
15 Correct 106 ms 220960 KB Output is correct
16 Correct 139 ms 220420 KB Output is correct
17 Correct 133 ms 220836 KB Output is correct
18 Correct 152 ms 221004 KB Output is correct
19 Correct 133 ms 225628 KB Output is correct
20 Correct 130 ms 224772 KB Output is correct
21 Correct 120 ms 225280 KB Output is correct
22 Correct 119 ms 225536 KB Output is correct
23 Correct 154 ms 221956 KB Output is correct
24 Correct 143 ms 222212 KB Output is correct
25 Correct 137 ms 227836 KB Output is correct
26 Correct 153 ms 221180 KB Output is correct
27 Correct 113 ms 221440 KB Output is correct
28 Correct 55 ms 199108 KB Output is correct
29 Correct 674 ms 199384 KB Output is correct
30 Correct 383 ms 199744 KB Output is correct
31 Correct 658 ms 199652 KB Output is correct
32 Correct 947 ms 199908 KB Output is correct
33 Correct 395 ms 199944 KB Output is correct
34 Correct 58 ms 199108 KB Output is correct
35 Correct 848 ms 230916 KB Output is correct
36 Correct 1029 ms 231116 KB Output is correct
37 Correct 1275 ms 230888 KB Output is correct
38 Correct 63 ms 199116 KB Output is correct
39 Execution timed out 3573 ms 229520 KB Time limit exceeded
40 Halted 0 ms 0 KB -