oj.uz

Submission #1040547

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

vector<int> g[500005];
vector<int> rg[500005];
int st[500005];
int dep[500005];
int ddep[500005];
int t;
int ett[1000005];
int rev[1000005];
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 < 1000005; 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))]);
        }
    }
}
pair<int,int> rmq(int l, int r){
    int d = r-l+1;
    int lg = 31 - __builtin_clz(d);
    return min(sparse[lg][l], sparse[lg][r-(1<<lg)+1]);
}
int lca(int u, int v){
    if(st[u] > st[v]) swap(u, v);
    return rmq(st[u], st[v]).second;
}
bool search(int a, int d){
    int l = lca(a, d);
    int dist = dep[a] + dep[d] - 2*dep[l];
    int ddist = ddep[d] - ddep[a];
    return dist == ddist;
}
vector<pair<int,int>> buffer;
const int THRESH = 2000;
int qs[500005];
int evp[500005];
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(buffer.size() >= THRESH){
        for(auto p : buffer) evp[p.first] += p.second;
        update(1);
        for(auto p : buffer) evp[p.first] -= p.second;
        buffer.clear();
    }
    int ret = qs[d];
    for(auto p : buffer){
        if(search(p.first, d)){
            ret += p.second;
        }
    }
    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;
        buffer.push_back({i, 1});
    }
    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]);
                buffer.push_back({ids[a], -1});
                buffer.push_back({ids[b], -1});
                last++;
                ids[a] = ids[b] = last;
                buffer.push_back({last, 2});
                break;
            case 1:
                a = get<1>(cmds[i]);
                d = get<2>(cmds[i]);
                if(search(ids[a], d)) cout << "yes" << endl;
                else cout << "no" << endl;
                break;
            case 2:
                d = get<1>(cmds[i]);
                cout << count(d) << endl;
                break;
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 151 ms 195012 KB Output is correct
2 Correct 162 ms 195548 KB Output is correct
3 Correct 160 ms 195768 KB Output is correct
4 Correct 165 ms 195804 KB Output is correct
5 Correct 158 ms 196096 KB Output is correct
6 Correct 154 ms 196100 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 151 ms 195012 KB Output is correct
2 Correct 162 ms 195548 KB Output is correct
3 Correct 160 ms 195768 KB Output is correct
4 Correct 165 ms 195804 KB Output is correct
5 Correct 158 ms 196096 KB Output is correct
6 Correct 154 ms 196100 KB Output is correct
7 Correct 160 ms 195032 KB Output is correct
8 Correct 678 ms 197340 KB Output is correct
9 Correct 468 ms 197720 KB Output is correct
10 Correct 626 ms 197672 KB Output is correct
11 Correct 890 ms 197916 KB Output is correct
12 Correct 628 ms 198208 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 149 ms 195020 KB Output is correct
2 Correct 228 ms 233220 KB Output is correct
3 Correct 209 ms 231168 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 149 ms 195020 KB Output is correct
2 Correct 228 ms 233220 KB Output is correct
3 Correct 209 ms 231168 KB Output is correct
4 Correct 155 ms 195036 KB Output is correct
5 Correct 1112 ms 229784 KB Output is correct
6 Correct 1575 ms 229824 KB Output is correct
7 Correct 1591 ms 229568 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 195016 KB Output is correct
2 Correct 234 ms 230404 KB Output is correct
3 Correct 235 ms 231680 KB Output is correct
4 Correct 206 ms 232444 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 195016 KB Output is correct
2 Correct 234 ms 230404 KB Output is correct
3 Correct 235 ms 231680 KB Output is correct
4 Correct 206 ms 232444 KB Output is correct
5 Correct 161 ms 195016 KB Output is correct
6 Correct 3294 ms 228096 KB Output is correct
7 Correct 883 ms 232548 KB Output is correct
8 Execution timed out 3576 ms 230760 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 195032 KB Output is correct
2 Correct 210 ms 221076 KB Output is correct
3 Correct 233 ms 220156 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 195032 KB Output is correct
2 Correct 210 ms 221076 KB Output is correct
3 Correct 233 ms 220156 KB Output is correct
4 Correct 152 ms 194924 KB Output is correct
5 Correct 824 ms 217848 KB Output is correct
6 Correct 1699 ms 221216 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 195028 KB Output is correct
2 Correct 229 ms 230628 KB Output is correct
3 Correct 243 ms 231516 KB Output is correct
4 Correct 209 ms 232192 KB Output is correct
5 Correct 143 ms 195016 KB Output is correct
6 Correct 201 ms 219716 KB Output is correct
7 Correct 243 ms 218880 KB Output is correct
8 Correct 241 ms 221088 KB Output is correct
9 Correct 238 ms 220420 KB Output is correct
10 Correct 222 ms 224596 KB Output is correct
11 Correct 225 ms 223492 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 195028 KB Output is correct
2 Correct 229 ms 230628 KB Output is correct
3 Correct 243 ms 231516 KB Output is correct
4 Correct 209 ms 232192 KB Output is correct
5 Correct 143 ms 195016 KB Output is correct
6 Correct 201 ms 219716 KB Output is correct
7 Correct 243 ms 218880 KB Output is correct
8 Correct 241 ms 221088 KB Output is correct
9 Correct 238 ms 220420 KB Output is correct
10 Correct 222 ms 224596 KB Output is correct
11 Correct 225 ms 223492 KB Output is correct
12 Correct 154 ms 195100 KB Output is correct
13 Correct 3197 ms 228084 KB Output is correct
14 Correct 831 ms 232528 KB Output is correct
15 Execution timed out 3559 ms 230592 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 195016 KB Output is correct
2 Correct 170 ms 195612 KB Output is correct
3 Correct 151 ms 195840 KB Output is correct
4 Correct 154 ms 195696 KB Output is correct
5 Correct 150 ms 196104 KB Output is correct
6 Correct 149 ms 195992 KB Output is correct
7 Correct 147 ms 195072 KB Output is correct
8 Correct 227 ms 231432 KB Output is correct
9 Correct 211 ms 232956 KB Output is correct
10 Correct 163 ms 195008 KB Output is correct
11 Correct 244 ms 231164 KB Output is correct
12 Correct 259 ms 230240 KB Output is correct
13 Correct 208 ms 232620 KB Output is correct
14 Correct 145 ms 195044 KB Output is correct
15 Correct 204 ms 220668 KB Output is correct
16 Correct 228 ms 219864 KB Output is correct
17 Correct 242 ms 220160 KB Output is correct
18 Correct 232 ms 220928 KB Output is correct
19 Correct 220 ms 225540 KB Output is correct
20 Correct 244 ms 224692 KB Output is correct
21 Correct 225 ms 224512 KB Output is correct
22 Correct 219 ms 224316 KB Output is correct
23 Correct 230 ms 222256 KB Output is correct
24 Correct 236 ms 220676 KB Output is correct
25 Correct 226 ms 226060 KB Output is correct
26 Correct 217 ms 219652 KB Output is correct
27 Correct 217 ms 220676 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 195016 KB Output is correct
2 Correct 170 ms 195612 KB Output is correct
3 Correct 151 ms 195840 KB Output is correct
4 Correct 154 ms 195696 KB Output is correct
5 Correct 150 ms 196104 KB Output is correct
6 Correct 149 ms 195992 KB Output is correct
7 Correct 147 ms 195072 KB Output is correct
8 Correct 227 ms 231432 KB Output is correct
9 Correct 211 ms 232956 KB Output is correct
10 Correct 163 ms 195008 KB Output is correct
11 Correct 244 ms 231164 KB Output is correct
12 Correct 259 ms 230240 KB Output is correct
13 Correct 208 ms 232620 KB Output is correct
14 Correct 145 ms 195044 KB Output is correct
15 Correct 204 ms 220668 KB Output is correct
16 Correct 228 ms 219864 KB Output is correct
17 Correct 242 ms 220160 KB Output is correct
18 Correct 232 ms 220928 KB Output is correct
19 Correct 220 ms 225540 KB Output is correct
20 Correct 244 ms 224692 KB Output is correct
21 Correct 225 ms 224512 KB Output is correct
22 Correct 219 ms 224316 KB Output is correct
23 Correct 230 ms 222256 KB Output is correct
24 Correct 236 ms 220676 KB Output is correct
25 Correct 226 ms 226060 KB Output is correct
26 Correct 217 ms 219652 KB Output is correct
27 Correct 217 ms 220676 KB Output is correct
28 Correct 151 ms 195020 KB Output is correct
29 Correct 656 ms 197416 KB Output is correct
30 Correct 472 ms 197892 KB Output is correct
31 Correct 604 ms 197856 KB Output is correct
32 Correct 873 ms 197888 KB Output is correct
33 Correct 642 ms 198144 KB Output is correct
34 Correct 166 ms 195012 KB Output is correct
35 Correct 1076 ms 229372 KB Output is correct
36 Correct 1533 ms 229636 KB Output is correct
37 Correct 1551 ms 229628 KB Output is correct
38 Correct 151 ms 195016 KB Output is correct
39 Correct 3447 ms 228244 KB Output is correct
40 Correct 804 ms 232504 KB Output is correct
41 Execution timed out 3569 ms 230796 KB Time limit exceeded
42 Halted 0 ms 0 KB -