oj.uz

Submission #1040554

# Submission time Handle Problem Language Result Execution time Memory
1040554 2024-08-01T07:20:22 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 234368 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

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))]);
        }
    }
}
inline pair<int,int> rmq(const int& l, const int& r){
    int d = r-l+1;
    int lg = 31 - __builtin_clz(d);
    return min(sparse[lg][l], sparse[lg][r-(1<<lg)+1]);
}
inline int lca(int u, int v){
    if(st[u] > st[v]) swap(u, v);
    return rmq(st[u], st[v]).second;
}
inline 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;
}
gp_hash_table<int, int> buffer;
const int THRESH = 750;
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[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]);
                buffer[ids[a]]--;
                buffer[ids[b]]--;
                last++;
                ids[a] = ids[b] = last;
                buffer[last] += 2;
                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 195012 KB Output is correct
2 Correct 67 ms 195800 KB Output is correct
3 Correct 58 ms 195840 KB Output is correct
4 Correct 64 ms 195800 KB Output is correct
5 Correct 57 ms 196008 KB Output is correct
6 Correct 57 ms 196096 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 195012 KB Output is correct
2 Correct 67 ms 195800 KB Output is correct
3 Correct 58 ms 195840 KB Output is correct
4 Correct 64 ms 195800 KB Output is correct
5 Correct 57 ms 196008 KB Output is correct
6 Correct 57 ms 196096 KB Output is correct
7 Correct 54 ms 195016 KB Output is correct
8 Correct 393 ms 197660 KB Output is correct
9 Correct 248 ms 198144 KB Output is correct
10 Correct 310 ms 197604 KB Output is correct
11 Correct 180 ms 197896 KB Output is correct
12 Correct 187 ms 198152 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 195132 KB Output is correct
2 Correct 116 ms 234132 KB Output is correct
3 Correct 117 ms 234112 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 195132 KB Output is correct
2 Correct 116 ms 234132 KB Output is correct
3 Correct 117 ms 234112 KB Output is correct
4 Correct 58 ms 195016 KB Output is correct
5 Correct 1481 ms 231556 KB Output is correct
6 Correct 1684 ms 231716 KB Output is correct
7 Correct 1714 ms 231548 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 195124 KB Output is correct
2 Correct 144 ms 232888 KB Output is correct
3 Correct 148 ms 233088 KB Output is correct
4 Correct 107 ms 234364 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 195124 KB Output is correct
2 Correct 144 ms 232888 KB Output is correct
3 Correct 148 ms 233088 KB Output is correct
4 Correct 107 ms 234364 KB Output is correct
5 Correct 57 ms 195100 KB Output is correct
6 Execution timed out 3553 ms 230344 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 194984 KB Output is correct
2 Correct 116 ms 222596 KB Output is correct
3 Correct 142 ms 222004 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 194984 KB Output is correct
2 Correct 116 ms 222596 KB Output is correct
3 Correct 142 ms 222004 KB Output is correct
4 Correct 55 ms 195044 KB Output is correct
5 Correct 1069 ms 220012 KB Output is correct
6 Correct 2303 ms 224128 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 195016 KB Output is correct
2 Correct 140 ms 233088 KB Output is correct
3 Correct 137 ms 233256 KB Output is correct
4 Correct 115 ms 234172 KB Output is correct
5 Correct 56 ms 195020 KB Output is correct
6 Correct 109 ms 222600 KB Output is correct
7 Correct 131 ms 221820 KB Output is correct
8 Correct 133 ms 222404 KB Output is correct
9 Correct 138 ms 222544 KB Output is correct
10 Correct 131 ms 227208 KB Output is correct
11 Correct 121 ms 226432 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 195016 KB Output is correct
2 Correct 140 ms 233088 KB Output is correct
3 Correct 137 ms 233256 KB Output is correct
4 Correct 115 ms 234172 KB Output is correct
5 Correct 56 ms 195020 KB Output is correct
6 Correct 109 ms 222600 KB Output is correct
7 Correct 131 ms 221820 KB Output is correct
8 Correct 133 ms 222404 KB Output is correct
9 Correct 138 ms 222544 KB Output is correct
10 Correct 131 ms 227208 KB Output is correct
11 Correct 121 ms 226432 KB Output is correct
12 Correct 55 ms 195016 KB Output is correct
13 Execution timed out 3534 ms 230424 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 195012 KB Output is correct
2 Correct 59 ms 195808 KB Output is correct
3 Correct 55 ms 195844 KB Output is correct
4 Correct 60 ms 195800 KB Output is correct
5 Correct 60 ms 196096 KB Output is correct
6 Correct 57 ms 196104 KB Output is correct
7 Correct 50 ms 195020 KB Output is correct
8 Correct 118 ms 234368 KB Output is correct
9 Correct 122 ms 234168 KB Output is correct
10 Correct 52 ms 194948 KB Output is correct
11 Correct 141 ms 233084 KB Output is correct
12 Correct 148 ms 233084 KB Output is correct
13 Correct 109 ms 234256 KB Output is correct
14 Correct 50 ms 195024 KB Output is correct
15 Correct 107 ms 222596 KB Output is correct
16 Correct 137 ms 221836 KB Output is correct
17 Correct 136 ms 222348 KB Output is correct
18 Correct 134 ms 222596 KB Output is correct
19 Correct 125 ms 227160 KB Output is correct
20 Correct 124 ms 226292 KB Output is correct
21 Correct 119 ms 226688 KB Output is correct
22 Correct 125 ms 227200 KB Output is correct
23 Correct 143 ms 223604 KB Output is correct
24 Correct 142 ms 223620 KB Output is correct
25 Correct 141 ms 228852 KB Output is correct
26 Correct 122 ms 222588 KB Output is correct
27 Correct 119 ms 223092 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 195012 KB Output is correct
2 Correct 59 ms 195808 KB Output is correct
3 Correct 55 ms 195844 KB Output is correct
4 Correct 60 ms 195800 KB Output is correct
5 Correct 60 ms 196096 KB Output is correct
6 Correct 57 ms 196104 KB Output is correct
7 Correct 50 ms 195020 KB Output is correct
8 Correct 118 ms 234368 KB Output is correct
9 Correct 122 ms 234168 KB Output is correct
10 Correct 52 ms 194948 KB Output is correct
11 Correct 141 ms 233084 KB Output is correct
12 Correct 148 ms 233084 KB Output is correct
13 Correct 109 ms 234256 KB Output is correct
14 Correct 50 ms 195024 KB Output is correct
15 Correct 107 ms 222596 KB Output is correct
16 Correct 137 ms 221836 KB Output is correct
17 Correct 136 ms 222348 KB Output is correct
18 Correct 134 ms 222596 KB Output is correct
19 Correct 125 ms 227160 KB Output is correct
20 Correct 124 ms 226292 KB Output is correct
21 Correct 119 ms 226688 KB Output is correct
22 Correct 125 ms 227200 KB Output is correct
23 Correct 143 ms 223604 KB Output is correct
24 Correct 142 ms 223620 KB Output is correct
25 Correct 141 ms 228852 KB Output is correct
26 Correct 122 ms 222588 KB Output is correct
27 Correct 119 ms 223092 KB Output is correct
28 Correct 61 ms 195016 KB Output is correct
29 Correct 372 ms 197592 KB Output is correct
30 Correct 239 ms 197892 KB Output is correct
31 Correct 283 ms 197604 KB Output is correct
32 Correct 189 ms 198156 KB Output is correct
33 Correct 192 ms 198084 KB Output is correct
34 Correct 56 ms 195012 KB Output is correct
35 Correct 1475 ms 231552 KB Output is correct
36 Correct 1699 ms 231676 KB Output is correct
37 Correct 1688 ms 231552 KB Output is correct
38 Correct 57 ms 195020 KB Output is correct
39 Execution timed out 3535 ms 230524 KB Time limit exceeded
40 Halted 0 ms 0 KB -