oj.uz

Submission #1040546

# Submission time Handle Problem Language Result Execution time Memory
1040546 2024-08-01T07:09:09 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 232956 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 = 1000;
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 169 ms 194976 KB Output is correct
2 Correct 157 ms 195716 KB Output is correct
3 Correct 180 ms 195828 KB Output is correct
4 Correct 174 ms 195732 KB Output is correct
5 Correct 183 ms 195972 KB Output is correct
6 Correct 169 ms 195992 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 169 ms 194976 KB Output is correct
2 Correct 157 ms 195716 KB Output is correct
3 Correct 180 ms 195828 KB Output is correct
4 Correct 174 ms 195732 KB Output is correct
5 Correct 183 ms 195972 KB Output is correct
6 Correct 169 ms 195992 KB Output is correct
7 Correct 168 ms 195024 KB Output is correct
8 Correct 432 ms 197348 KB Output is correct
9 Correct 318 ms 197848 KB Output is correct
10 Correct 400 ms 197484 KB Output is correct
11 Correct 538 ms 197820 KB Output is correct
12 Correct 442 ms 198148 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 195 ms 195016 KB Output is correct
2 Correct 228 ms 232368 KB Output is correct
3 Correct 230 ms 231744 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 195 ms 195016 KB Output is correct
2 Correct 228 ms 232368 KB Output is correct
3 Correct 230 ms 231744 KB Output is correct
4 Correct 157 ms 195160 KB Output is correct
5 Correct 1964 ms 229632 KB Output is correct
6 Correct 1951 ms 229632 KB Output is correct
7 Correct 1957 ms 229680 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 195016 KB Output is correct
2 Correct 231 ms 231520 KB Output is correct
3 Correct 240 ms 231424 KB Output is correct
4 Correct 203 ms 231920 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 195016 KB Output is correct
2 Correct 231 ms 231520 KB Output is correct
3 Correct 240 ms 231424 KB Output is correct
4 Correct 203 ms 231920 KB Output is correct
5 Correct 150 ms 195020 KB Output is correct
6 Execution timed out 3505 ms 228096 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 195060 KB Output is correct
2 Correct 218 ms 220668 KB Output is correct
3 Correct 233 ms 218880 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 195060 KB Output is correct
2 Correct 218 ms 220668 KB Output is correct
3 Correct 233 ms 218880 KB Output is correct
4 Correct 153 ms 195240 KB Output is correct
5 Correct 1008 ms 217856 KB Output is correct
6 Correct 1860 ms 220404 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 195012 KB Output is correct
2 Correct 231 ms 231828 KB Output is correct
3 Correct 237 ms 230408 KB Output is correct
4 Correct 203 ms 231320 KB Output is correct
5 Correct 149 ms 195012 KB Output is correct
6 Correct 212 ms 220684 KB Output is correct
7 Correct 225 ms 219416 KB Output is correct
8 Correct 246 ms 220416 KB Output is correct
9 Correct 237 ms 219652 KB Output is correct
10 Correct 216 ms 224260 KB Output is correct
11 Correct 218 ms 224256 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 195012 KB Output is correct
2 Correct 231 ms 231828 KB Output is correct
3 Correct 237 ms 230408 KB Output is correct
4 Correct 203 ms 231320 KB Output is correct
5 Correct 149 ms 195012 KB Output is correct
6 Correct 212 ms 220684 KB Output is correct
7 Correct 225 ms 219416 KB Output is correct
8 Correct 246 ms 220416 KB Output is correct
9 Correct 237 ms 219652 KB Output is correct
10 Correct 216 ms 224260 KB Output is correct
11 Correct 218 ms 224256 KB Output is correct
12 Correct 158 ms 195012 KB Output is correct
13 Execution timed out 3507 ms 228096 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 195016 KB Output is correct
2 Correct 151 ms 195548 KB Output is correct
3 Correct 160 ms 195844 KB Output is correct
4 Correct 153 ms 195768 KB Output is correct
5 Correct 159 ms 196044 KB Output is correct
6 Correct 151 ms 196072 KB Output is correct
7 Correct 150 ms 195248 KB Output is correct
8 Correct 209 ms 231680 KB Output is correct
9 Correct 207 ms 232956 KB Output is correct
10 Correct 152 ms 195016 KB Output is correct
11 Correct 232 ms 230080 KB Output is correct
12 Correct 229 ms 230400 KB Output is correct
13 Correct 209 ms 231696 KB Output is correct
14 Correct 148 ms 195020 KB Output is correct
15 Correct 203 ms 220416 KB Output is correct
16 Correct 243 ms 220660 KB Output is correct
17 Correct 228 ms 220672 KB Output is correct
18 Correct 225 ms 220928 KB Output is correct
19 Correct 222 ms 225356 KB Output is correct
20 Correct 220 ms 224000 KB Output is correct
21 Correct 212 ms 224764 KB Output is correct
22 Correct 213 ms 225788 KB Output is correct
23 Correct 231 ms 221184 KB Output is correct
24 Correct 253 ms 221440 KB Output is correct
25 Correct 227 ms 226564 KB Output is correct
26 Correct 216 ms 221064 KB Output is correct
27 Correct 225 ms 220676 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 145 ms 195016 KB Output is correct
2 Correct 151 ms 195548 KB Output is correct
3 Correct 160 ms 195844 KB Output is correct
4 Correct 153 ms 195768 KB Output is correct
5 Correct 159 ms 196044 KB Output is correct
6 Correct 151 ms 196072 KB Output is correct
7 Correct 150 ms 195248 KB Output is correct
8 Correct 209 ms 231680 KB Output is correct
9 Correct 207 ms 232956 KB Output is correct
10 Correct 152 ms 195016 KB Output is correct
11 Correct 232 ms 230080 KB Output is correct
12 Correct 229 ms 230400 KB Output is correct
13 Correct 209 ms 231696 KB Output is correct
14 Correct 148 ms 195020 KB Output is correct
15 Correct 203 ms 220416 KB Output is correct
16 Correct 243 ms 220660 KB Output is correct
17 Correct 228 ms 220672 KB Output is correct
18 Correct 225 ms 220928 KB Output is correct
19 Correct 222 ms 225356 KB Output is correct
20 Correct 220 ms 224000 KB Output is correct
21 Correct 212 ms 224764 KB Output is correct
22 Correct 213 ms 225788 KB Output is correct
23 Correct 231 ms 221184 KB Output is correct
24 Correct 253 ms 221440 KB Output is correct
25 Correct 227 ms 226564 KB Output is correct
26 Correct 216 ms 221064 KB Output is correct
27 Correct 225 ms 220676 KB Output is correct
28 Correct 152 ms 194972 KB Output is correct
29 Correct 396 ms 197344 KB Output is correct
30 Correct 310 ms 197892 KB Output is correct
31 Correct 370 ms 197596 KB Output is correct
32 Correct 487 ms 197888 KB Output is correct
33 Correct 390 ms 198144 KB Output is correct
34 Correct 151 ms 195004 KB Output is correct
35 Correct 1630 ms 229564 KB Output is correct
36 Correct 1882 ms 229888 KB Output is correct
37 Correct 2025 ms 229700 KB Output is correct
38 Correct 150 ms 195016 KB Output is correct
39 Execution timed out 3543 ms 228116 KB Time limit exceeded
40 Halted 0 ms 0 KB -