oj.uz

Submission #1040559

# Submission time Handle Problem Language Result Execution time Memory
1040559 2024-08-01T07:23:13 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 234372 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 = 1100;
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 54 ms 195008 KB Output is correct
2 Correct 57 ms 195808 KB Output is correct
3 Correct 57 ms 195844 KB Output is correct
4 Correct 56 ms 195804 KB Output is correct
5 Correct 59 ms 196080 KB Output is correct
6 Correct 58 ms 196288 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 195008 KB Output is correct
2 Correct 57 ms 195808 KB Output is correct
3 Correct 57 ms 195844 KB Output is correct
4 Correct 56 ms 195804 KB Output is correct
5 Correct 59 ms 196080 KB Output is correct
6 Correct 58 ms 196288 KB Output is correct
7 Correct 57 ms 194972 KB Output is correct
8 Correct 554 ms 197656 KB Output is correct
9 Correct 338 ms 197888 KB Output is correct
10 Correct 435 ms 197604 KB Output is correct
11 Correct 208 ms 197912 KB Output is correct
12 Correct 174 ms 198068 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 195020 KB Output is correct
2 Correct 116 ms 234112 KB Output is correct
3 Correct 114 ms 234280 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 195020 KB Output is correct
2 Correct 116 ms 234112 KB Output is correct
3 Correct 114 ms 234280 KB Output is correct
4 Correct 64 ms 194968 KB Output is correct
5 Correct 1148 ms 231696 KB Output is correct
6 Correct 1362 ms 231556 KB Output is correct
7 Correct 1337 ms 231548 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 195020 KB Output is correct
2 Correct 140 ms 233088 KB Output is correct
3 Correct 144 ms 233052 KB Output is correct
4 Correct 113 ms 234116 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 195020 KB Output is correct
2 Correct 140 ms 233088 KB Output is correct
3 Correct 144 ms 233052 KB Output is correct
4 Correct 113 ms 234116 KB Output is correct
5 Correct 55 ms 195016 KB Output is correct
6 Execution timed out 3573 ms 230428 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 195016 KB Output is correct
2 Correct 109 ms 222596 KB Output is correct
3 Correct 132 ms 221820 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 195016 KB Output is correct
2 Correct 109 ms 222596 KB Output is correct
3 Correct 132 ms 221820 KB Output is correct
4 Correct 54 ms 195020 KB Output is correct
5 Correct 803 ms 220032 KB Output is correct
6 Correct 1950 ms 224008 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 195016 KB Output is correct
2 Correct 141 ms 233088 KB Output is correct
3 Correct 141 ms 233088 KB Output is correct
4 Correct 108 ms 234168 KB Output is correct
5 Correct 54 ms 195160 KB Output is correct
6 Correct 117 ms 222724 KB Output is correct
7 Correct 137 ms 222016 KB Output is correct
8 Correct 132 ms 222336 KB Output is correct
9 Correct 147 ms 222336 KB Output is correct
10 Correct 124 ms 227200 KB Output is correct
11 Correct 149 ms 226432 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 195016 KB Output is correct
2 Correct 141 ms 233088 KB Output is correct
3 Correct 141 ms 233088 KB Output is correct
4 Correct 108 ms 234168 KB Output is correct
5 Correct 54 ms 195160 KB Output is correct
6 Correct 117 ms 222724 KB Output is correct
7 Correct 137 ms 222016 KB Output is correct
8 Correct 132 ms 222336 KB Output is correct
9 Correct 147 ms 222336 KB Output is correct
10 Correct 124 ms 227200 KB Output is correct
11 Correct 149 ms 226432 KB Output is correct
12 Correct 54 ms 194904 KB Output is correct
13 Execution timed out 3552 ms 230528 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 195012 KB Output is correct
2 Correct 67 ms 195788 KB Output is correct
3 Correct 55 ms 195908 KB Output is correct
4 Correct 57 ms 195808 KB Output is correct
5 Correct 58 ms 196092 KB Output is correct
6 Correct 55 ms 196104 KB Output is correct
7 Correct 59 ms 194996 KB Output is correct
8 Correct 119 ms 234372 KB Output is correct
9 Correct 118 ms 234112 KB Output is correct
10 Correct 51 ms 195016 KB Output is correct
11 Correct 146 ms 233088 KB Output is correct
12 Correct 143 ms 232980 KB Output is correct
13 Correct 111 ms 234116 KB Output is correct
14 Correct 55 ms 194960 KB Output is correct
15 Correct 114 ms 222596 KB Output is correct
16 Correct 138 ms 222028 KB Output is correct
17 Correct 137 ms 222332 KB Output is correct
18 Correct 152 ms 222592 KB Output is correct
19 Correct 125 ms 227200 KB Output is correct
20 Correct 124 ms 226436 KB Output is correct
21 Correct 121 ms 226936 KB Output is correct
22 Correct 120 ms 227204 KB Output is correct
23 Correct 136 ms 223356 KB Output is correct
24 Correct 135 ms 223592 KB Output is correct
25 Correct 129 ms 228996 KB Output is correct
26 Correct 129 ms 222596 KB Output is correct
27 Correct 114 ms 222848 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 195012 KB Output is correct
2 Correct 67 ms 195788 KB Output is correct
3 Correct 55 ms 195908 KB Output is correct
4 Correct 57 ms 195808 KB Output is correct
5 Correct 58 ms 196092 KB Output is correct
6 Correct 55 ms 196104 KB Output is correct
7 Correct 59 ms 194996 KB Output is correct
8 Correct 119 ms 234372 KB Output is correct
9 Correct 118 ms 234112 KB Output is correct
10 Correct 51 ms 195016 KB Output is correct
11 Correct 146 ms 233088 KB Output is correct
12 Correct 143 ms 232980 KB Output is correct
13 Correct 111 ms 234116 KB Output is correct
14 Correct 55 ms 194960 KB Output is correct
15 Correct 114 ms 222596 KB Output is correct
16 Correct 138 ms 222028 KB Output is correct
17 Correct 137 ms 222332 KB Output is correct
18 Correct 152 ms 222592 KB Output is correct
19 Correct 125 ms 227200 KB Output is correct
20 Correct 124 ms 226436 KB Output is correct
21 Correct 121 ms 226936 KB Output is correct
22 Correct 120 ms 227204 KB Output is correct
23 Correct 136 ms 223356 KB Output is correct
24 Correct 135 ms 223592 KB Output is correct
25 Correct 129 ms 228996 KB Output is correct
26 Correct 129 ms 222596 KB Output is correct
27 Correct 114 ms 222848 KB Output is correct
28 Correct 55 ms 195024 KB Output is correct
29 Correct 539 ms 197652 KB Output is correct
30 Correct 356 ms 198088 KB Output is correct
31 Correct 444 ms 197732 KB Output is correct
32 Correct 208 ms 198004 KB Output is correct
33 Correct 192 ms 198152 KB Output is correct
34 Correct 60 ms 195020 KB Output is correct
35 Correct 1168 ms 231760 KB Output is correct
36 Correct 1403 ms 231792 KB Output is correct
37 Correct 1439 ms 231740 KB Output is correct
38 Correct 55 ms 195016 KB Output is correct
39 Execution timed out 3551 ms 230272 KB Time limit exceeded
40 Halted 0 ms 0 KB -