oj.uz

Submission #1040544

# Submission time Handle Problem Language Result Execution time Memory
1040544 2024-08-01T07:07:52 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 232704 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 = 500;
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 146 ms 195016 KB Output is correct
2 Correct 151 ms 195620 KB Output is correct
3 Correct 153 ms 195928 KB Output is correct
4 Correct 154 ms 196080 KB Output is correct
5 Correct 166 ms 196100 KB Output is correct
6 Correct 149 ms 196100 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 146 ms 195016 KB Output is correct
2 Correct 151 ms 195620 KB Output is correct
3 Correct 153 ms 195928 KB Output is correct
4 Correct 154 ms 196080 KB Output is correct
5 Correct 166 ms 196100 KB Output is correct
6 Correct 149 ms 196100 KB Output is correct
7 Correct 161 ms 195044 KB Output is correct
8 Correct 290 ms 197524 KB Output is correct
9 Correct 231 ms 197888 KB Output is correct
10 Correct 267 ms 197600 KB Output is correct
11 Correct 297 ms 197964 KB Output is correct
12 Correct 279 ms 198300 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 195016 KB Output is correct
2 Correct 215 ms 231372 KB Output is correct
3 Correct 213 ms 232212 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 195016 KB Output is correct
2 Correct 215 ms 231372 KB Output is correct
3 Correct 213 ms 232212 KB Output is correct
4 Correct 156 ms 194936 KB Output is correct
5 Correct 3063 ms 229572 KB Output is correct
6 Correct 3085 ms 231516 KB Output is correct
7 Correct 3190 ms 231424 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 195056 KB Output is correct
2 Correct 247 ms 231420 KB Output is correct
3 Correct 233 ms 231168 KB Output is correct
4 Correct 203 ms 232704 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 195056 KB Output is correct
2 Correct 247 ms 231420 KB Output is correct
3 Correct 233 ms 231168 KB Output is correct
4 Correct 203 ms 232704 KB Output is correct
5 Correct 157 ms 195064 KB Output is correct
6 Execution timed out 3581 ms 227844 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 195068 KB Output is correct
2 Correct 200 ms 220276 KB Output is correct
3 Correct 226 ms 219908 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 195068 KB Output is correct
2 Correct 200 ms 220276 KB Output is correct
3 Correct 226 ms 219908 KB Output is correct
4 Correct 156 ms 195528 KB Output is correct
5 Correct 1551 ms 217752 KB Output is correct
6 Correct 2787 ms 220840 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 155 ms 195268 KB Output is correct
2 Correct 235 ms 231424 KB Output is correct
3 Correct 226 ms 230892 KB Output is correct
4 Correct 206 ms 231424 KB Output is correct
5 Correct 146 ms 195020 KB Output is correct
6 Correct 218 ms 220844 KB Output is correct
7 Correct 239 ms 219284 KB Output is correct
8 Correct 241 ms 220684 KB Output is correct
9 Correct 231 ms 221188 KB Output is correct
10 Correct 221 ms 224468 KB Output is correct
11 Correct 227 ms 224256 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 155 ms 195268 KB Output is correct
2 Correct 235 ms 231424 KB Output is correct
3 Correct 226 ms 230892 KB Output is correct
4 Correct 206 ms 231424 KB Output is correct
5 Correct 146 ms 195020 KB Output is correct
6 Correct 218 ms 220844 KB Output is correct
7 Correct 239 ms 219284 KB Output is correct
8 Correct 241 ms 220684 KB Output is correct
9 Correct 231 ms 221188 KB Output is correct
10 Correct 221 ms 224468 KB Output is correct
11 Correct 227 ms 224256 KB Output is correct
12 Correct 155 ms 195120 KB Output is correct
13 Execution timed out 3519 ms 228212 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 144 ms 195064 KB Output is correct
2 Correct 176 ms 195544 KB Output is correct
3 Correct 165 ms 195844 KB Output is correct
4 Correct 160 ms 195656 KB Output is correct
5 Correct 152 ms 196100 KB Output is correct
6 Correct 156 ms 196104 KB Output is correct
7 Correct 149 ms 195012 KB Output is correct
8 Correct 230 ms 231864 KB Output is correct
9 Correct 220 ms 231940 KB Output is correct
10 Correct 149 ms 195016 KB Output is correct
11 Correct 236 ms 231648 KB Output is correct
12 Correct 230 ms 230552 KB Output is correct
13 Correct 206 ms 231768 KB Output is correct
14 Correct 146 ms 195012 KB Output is correct
15 Correct 199 ms 220420 KB Output is correct
16 Correct 226 ms 220416 KB Output is correct
17 Correct 234 ms 220332 KB Output is correct
18 Correct 228 ms 221184 KB Output is correct
19 Correct 218 ms 226048 KB Output is correct
20 Correct 222 ms 223836 KB Output is correct
21 Correct 225 ms 225120 KB Output is correct
22 Correct 217 ms 226020 KB Output is correct
23 Correct 262 ms 222408 KB Output is correct
24 Correct 226 ms 221036 KB Output is correct
25 Correct 229 ms 226928 KB Output is correct
26 Correct 223 ms 221180 KB Output is correct
27 Correct 214 ms 219900 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 144 ms 195064 KB Output is correct
2 Correct 176 ms 195544 KB Output is correct
3 Correct 165 ms 195844 KB Output is correct
4 Correct 160 ms 195656 KB Output is correct
5 Correct 152 ms 196100 KB Output is correct
6 Correct 156 ms 196104 KB Output is correct
7 Correct 149 ms 195012 KB Output is correct
8 Correct 230 ms 231864 KB Output is correct
9 Correct 220 ms 231940 KB Output is correct
10 Correct 149 ms 195016 KB Output is correct
11 Correct 236 ms 231648 KB Output is correct
12 Correct 230 ms 230552 KB Output is correct
13 Correct 206 ms 231768 KB Output is correct
14 Correct 146 ms 195012 KB Output is correct
15 Correct 199 ms 220420 KB Output is correct
16 Correct 226 ms 220416 KB Output is correct
17 Correct 234 ms 220332 KB Output is correct
18 Correct 228 ms 221184 KB Output is correct
19 Correct 218 ms 226048 KB Output is correct
20 Correct 222 ms 223836 KB Output is correct
21 Correct 225 ms 225120 KB Output is correct
22 Correct 217 ms 226020 KB Output is correct
23 Correct 262 ms 222408 KB Output is correct
24 Correct 226 ms 221036 KB Output is correct
25 Correct 229 ms 226928 KB Output is correct
26 Correct 223 ms 221180 KB Output is correct
27 Correct 214 ms 219900 KB Output is correct
28 Correct 174 ms 195060 KB Output is correct
29 Correct 275 ms 197440 KB Output is correct
30 Correct 236 ms 197768 KB Output is correct
31 Correct 280 ms 197600 KB Output is correct
32 Correct 301 ms 197880 KB Output is correct
33 Correct 271 ms 197908 KB Output is correct
34 Correct 155 ms 195044 KB Output is correct
35 Correct 2938 ms 229444 KB Output is correct
36 Correct 3173 ms 231308 KB Output is correct
37 Correct 3093 ms 231612 KB Output is correct
38 Correct 150 ms 195932 KB Output is correct
39 Execution timed out 3536 ms 230864 KB Time limit exceeded
40 Halted 0 ms 0 KB -