oj.uz

Submission #1040679

# Submission time Handle Problem Language Result Execution time Memory
1040679 2024-08-01T08:25:51 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 232804 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 = st[a];
    int r = st[d];
    if(l > r){
        l = st[d];
        r = st[a];
    }
    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 58 ms 199112 KB Output is correct
2 Correct 58 ms 199552 KB Output is correct
3 Correct 79 ms 199660 KB Output is correct
4 Correct 65 ms 199656 KB Output is correct
5 Correct 67 ms 199920 KB Output is correct
6 Correct 61 ms 199904 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 199112 KB Output is correct
2 Correct 58 ms 199552 KB Output is correct
3 Correct 79 ms 199660 KB Output is correct
4 Correct 65 ms 199656 KB Output is correct
5 Correct 67 ms 199920 KB Output is correct
6 Correct 61 ms 199904 KB Output is correct
7 Correct 58 ms 199108 KB Output is correct
8 Correct 702 ms 199384 KB Output is correct
9 Correct 398 ms 199688 KB Output is correct
10 Correct 677 ms 199632 KB Output is correct
11 Correct 1045 ms 200276 KB Output is correct
12 Correct 428 ms 200004 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 199148 KB Output is correct
2 Correct 115 ms 232716 KB Output is correct
3 Correct 130 ms 232764 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 199148 KB Output is correct
2 Correct 115 ms 232716 KB Output is correct
3 Correct 130 ms 232764 KB Output is correct
4 Correct 57 ms 199084 KB Output is correct
5 Correct 854 ms 230940 KB Output is correct
6 Correct 1157 ms 231048 KB Output is correct
7 Correct 1311 ms 230912 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 199080 KB Output is correct
2 Correct 147 ms 231628 KB Output is correct
3 Correct 158 ms 231424 KB Output is correct
4 Correct 125 ms 232704 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 199080 KB Output is correct
2 Correct 147 ms 231628 KB Output is correct
3 Correct 158 ms 231424 KB Output is correct
4 Correct 125 ms 232704 KB Output is correct
5 Correct 67 ms 199048 KB Output is correct
6 Correct 3253 ms 229480 KB Output is correct
7 Correct 693 ms 231176 KB Output is correct
8 Execution timed out 3550 ms 229568 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 199132 KB Output is correct
2 Correct 106 ms 221288 KB Output is correct
3 Correct 155 ms 220416 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 199132 KB Output is correct
2 Correct 106 ms 221288 KB Output is correct
3 Correct 155 ms 220416 KB Output is correct
4 Correct 53 ms 199104 KB Output is correct
5 Correct 927 ms 219228 KB Output is correct
6 Correct 1995 ms 220624 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 71 ms 199112 KB Output is correct
2 Correct 147 ms 231432 KB Output is correct
3 Correct 144 ms 231388 KB Output is correct
4 Correct 109 ms 232736 KB Output is correct
5 Correct 56 ms 199180 KB Output is correct
6 Correct 149 ms 221144 KB Output is correct
7 Correct 137 ms 220452 KB Output is correct
8 Correct 142 ms 220788 KB Output is correct
9 Correct 145 ms 220916 KB Output is correct
10 Correct 130 ms 225764 KB Output is correct
11 Correct 127 ms 224724 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 71 ms 199112 KB Output is correct
2 Correct 147 ms 231432 KB Output is correct
3 Correct 144 ms 231388 KB Output is correct
4 Correct 109 ms 232736 KB Output is correct
5 Correct 56 ms 199180 KB Output is correct
6 Correct 149 ms 221144 KB Output is correct
7 Correct 137 ms 220452 KB Output is correct
8 Correct 142 ms 220788 KB Output is correct
9 Correct 145 ms 220916 KB Output is correct
10 Correct 130 ms 225764 KB Output is correct
11 Correct 127 ms 224724 KB Output is correct
12 Correct 55 ms 199140 KB Output is correct
13 Correct 3179 ms 229476 KB Output is correct
14 Correct 679 ms 230916 KB Output is correct
15 Execution timed out 3559 ms 229628 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 199112 KB Output is correct
2 Correct 63 ms 199456 KB Output is correct
3 Correct 65 ms 199788 KB Output is correct
4 Correct 69 ms 199496 KB Output is correct
5 Correct 74 ms 199956 KB Output is correct
6 Correct 69 ms 199924 KB Output is correct
7 Correct 72 ms 199012 KB Output is correct
8 Correct 124 ms 232628 KB Output is correct
9 Correct 119 ms 232688 KB Output is correct
10 Correct 53 ms 199172 KB Output is correct
11 Correct 169 ms 231388 KB Output is correct
12 Correct 179 ms 231420 KB Output is correct
13 Correct 132 ms 232804 KB Output is correct
14 Correct 57 ms 199080 KB Output is correct
15 Correct 117 ms 221048 KB Output is correct
16 Correct 150 ms 220444 KB Output is correct
17 Correct 178 ms 220772 KB Output is correct
18 Correct 176 ms 220928 KB Output is correct
19 Correct 155 ms 225536 KB Output is correct
20 Correct 161 ms 224812 KB Output is correct
21 Correct 163 ms 225348 KB Output is correct
22 Correct 154 ms 225648 KB Output is correct
23 Correct 166 ms 221900 KB Output is correct
24 Correct 188 ms 222208 KB Output is correct
25 Correct 153 ms 227412 KB Output is correct
26 Correct 166 ms 221320 KB Output is correct
27 Correct 137 ms 221444 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 199112 KB Output is correct
2 Correct 63 ms 199456 KB Output is correct
3 Correct 65 ms 199788 KB Output is correct
4 Correct 69 ms 199496 KB Output is correct
5 Correct 74 ms 199956 KB Output is correct
6 Correct 69 ms 199924 KB Output is correct
7 Correct 72 ms 199012 KB Output is correct
8 Correct 124 ms 232628 KB Output is correct
9 Correct 119 ms 232688 KB Output is correct
10 Correct 53 ms 199172 KB Output is correct
11 Correct 169 ms 231388 KB Output is correct
12 Correct 179 ms 231420 KB Output is correct
13 Correct 132 ms 232804 KB Output is correct
14 Correct 57 ms 199080 KB Output is correct
15 Correct 117 ms 221048 KB Output is correct
16 Correct 150 ms 220444 KB Output is correct
17 Correct 178 ms 220772 KB Output is correct
18 Correct 176 ms 220928 KB Output is correct
19 Correct 155 ms 225536 KB Output is correct
20 Correct 161 ms 224812 KB Output is correct
21 Correct 163 ms 225348 KB Output is correct
22 Correct 154 ms 225648 KB Output is correct
23 Correct 166 ms 221900 KB Output is correct
24 Correct 188 ms 222208 KB Output is correct
25 Correct 153 ms 227412 KB Output is correct
26 Correct 166 ms 221320 KB Output is correct
27 Correct 137 ms 221444 KB Output is correct
28 Correct 60 ms 199092 KB Output is correct
29 Correct 769 ms 199388 KB Output is correct
30 Correct 426 ms 199728 KB Output is correct
31 Correct 787 ms 199856 KB Output is correct
32 Correct 1112 ms 199944 KB Output is correct
33 Correct 480 ms 199860 KB Output is correct
34 Correct 63 ms 199068 KB Output is correct
35 Correct 992 ms 231132 KB Output is correct
36 Correct 1270 ms 231152 KB Output is correct
37 Correct 1438 ms 231072 KB Output is correct
38 Correct 56 ms 199112 KB Output is correct
39 Execution timed out 3571 ms 229380 KB Time limit exceeded
40 Halted 0 ms 0 KB -