oj.uz

Submission #1040561

# Submission time Handle Problem Language Result Execution time Memory
1040561 2024-08-01T07:25:46 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 = 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[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 56 ms 195156 KB Output is correct
2 Correct 58 ms 195628 KB Output is correct
3 Correct 59 ms 196056 KB Output is correct
4 Correct 61 ms 195776 KB Output is correct
5 Correct 56 ms 196132 KB Output is correct
6 Correct 58 ms 196292 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 195156 KB Output is correct
2 Correct 58 ms 195628 KB Output is correct
3 Correct 59 ms 196056 KB Output is correct
4 Correct 61 ms 195776 KB Output is correct
5 Correct 56 ms 196132 KB Output is correct
6 Correct 58 ms 196292 KB Output is correct
7 Correct 57 ms 195012 KB Output is correct
8 Correct 1036 ms 197600 KB Output is correct
9 Correct 544 ms 197888 KB Output is correct
10 Correct 851 ms 197600 KB Output is correct
11 Correct 451 ms 197844 KB Output is correct
12 Correct 522 ms 198312 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 195020 KB Output is correct
2 Correct 120 ms 234208 KB Output is correct
3 Correct 114 ms 234372 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 195020 KB Output is correct
2 Correct 120 ms 234208 KB Output is correct
3 Correct 114 ms 234372 KB Output is correct
4 Correct 53 ms 195016 KB Output is correct
5 Correct 813 ms 231628 KB Output is correct
6 Correct 1355 ms 231640 KB Output is correct
7 Correct 1376 ms 231548 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 195012 KB Output is correct
2 Correct 142 ms 232992 KB Output is correct
3 Correct 150 ms 233084 KB Output is correct
4 Correct 123 ms 234236 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 195012 KB Output is correct
2 Correct 142 ms 232992 KB Output is correct
3 Correct 150 ms 233084 KB Output is correct
4 Correct 123 ms 234236 KB Output is correct
5 Correct 59 ms 195032 KB Output is correct
6 Correct 3347 ms 230400 KB Output is correct
7 Correct 731 ms 231552 KB Output is correct
8 Execution timed out 3561 ms 230532 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 195016 KB Output is correct
2 Correct 108 ms 222596 KB Output is correct
3 Correct 132 ms 221988 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 195016 KB Output is correct
2 Correct 108 ms 222596 KB Output is correct
3 Correct 132 ms 221988 KB Output is correct
4 Correct 83 ms 195020 KB Output is correct
5 Correct 855 ms 220036 KB Output is correct
6 Correct 2135 ms 224120 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 80 ms 195092 KB Output is correct
2 Correct 155 ms 233092 KB Output is correct
3 Correct 179 ms 233040 KB Output is correct
4 Correct 108 ms 234316 KB Output is correct
5 Correct 51 ms 195096 KB Output is correct
6 Correct 107 ms 222404 KB Output is correct
7 Correct 128 ms 221932 KB Output is correct
8 Correct 172 ms 222332 KB Output is correct
9 Correct 141 ms 222448 KB Output is correct
10 Correct 121 ms 227200 KB Output is correct
11 Correct 132 ms 226512 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 80 ms 195092 KB Output is correct
2 Correct 155 ms 233092 KB Output is correct
3 Correct 179 ms 233040 KB Output is correct
4 Correct 108 ms 234316 KB Output is correct
5 Correct 51 ms 195096 KB Output is correct
6 Correct 107 ms 222404 KB Output is correct
7 Correct 128 ms 221932 KB Output is correct
8 Correct 172 ms 222332 KB Output is correct
9 Correct 141 ms 222448 KB Output is correct
10 Correct 121 ms 227200 KB Output is correct
11 Correct 132 ms 226512 KB Output is correct
12 Correct 57 ms 195012 KB Output is correct
13 Execution timed out 3586 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 67 ms 195016 KB Output is correct
2 Correct 66 ms 195668 KB Output is correct
3 Correct 63 ms 195848 KB Output is correct
4 Correct 61 ms 195988 KB Output is correct
5 Correct 62 ms 196012 KB Output is correct
6 Correct 60 ms 196328 KB Output is correct
7 Correct 56 ms 195140 KB Output is correct
8 Correct 122 ms 234140 KB Output is correct
9 Correct 123 ms 234112 KB Output is correct
10 Correct 50 ms 195020 KB Output is correct
11 Correct 139 ms 232976 KB Output is correct
12 Correct 135 ms 233056 KB Output is correct
13 Correct 106 ms 234304 KB Output is correct
14 Correct 83 ms 195016 KB Output is correct
15 Correct 111 ms 222596 KB Output is correct
16 Correct 134 ms 221872 KB Output is correct
17 Correct 131 ms 222352 KB Output is correct
18 Correct 140 ms 222332 KB Output is correct
19 Correct 125 ms 227188 KB Output is correct
20 Correct 126 ms 226444 KB Output is correct
21 Correct 129 ms 226880 KB Output is correct
22 Correct 123 ms 227204 KB Output is correct
23 Correct 138 ms 223360 KB Output is correct
24 Correct 139 ms 224128 KB Output is correct
25 Correct 128 ms 229000 KB Output is correct
26 Correct 122 ms 222616 KB Output is correct
27 Correct 116 ms 222848 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 67 ms 195016 KB Output is correct
2 Correct 66 ms 195668 KB Output is correct
3 Correct 63 ms 195848 KB Output is correct
4 Correct 61 ms 195988 KB Output is correct
5 Correct 62 ms 196012 KB Output is correct
6 Correct 60 ms 196328 KB Output is correct
7 Correct 56 ms 195140 KB Output is correct
8 Correct 122 ms 234140 KB Output is correct
9 Correct 123 ms 234112 KB Output is correct
10 Correct 50 ms 195020 KB Output is correct
11 Correct 139 ms 232976 KB Output is correct
12 Correct 135 ms 233056 KB Output is correct
13 Correct 106 ms 234304 KB Output is correct
14 Correct 83 ms 195016 KB Output is correct
15 Correct 111 ms 222596 KB Output is correct
16 Correct 134 ms 221872 KB Output is correct
17 Correct 131 ms 222352 KB Output is correct
18 Correct 140 ms 222332 KB Output is correct
19 Correct 125 ms 227188 KB Output is correct
20 Correct 126 ms 226444 KB Output is correct
21 Correct 129 ms 226880 KB Output is correct
22 Correct 123 ms 227204 KB Output is correct
23 Correct 138 ms 223360 KB Output is correct
24 Correct 139 ms 224128 KB Output is correct
25 Correct 128 ms 229000 KB Output is correct
26 Correct 122 ms 222616 KB Output is correct
27 Correct 116 ms 222848 KB Output is correct
28 Correct 55 ms 195016 KB Output is correct
29 Correct 1002 ms 197596 KB Output is correct
30 Correct 558 ms 197904 KB Output is correct
31 Correct 849 ms 197604 KB Output is correct
32 Correct 463 ms 197888 KB Output is correct
33 Correct 549 ms 198280 KB Output is correct
34 Correct 56 ms 195016 KB Output is correct
35 Correct 869 ms 231552 KB Output is correct
36 Correct 1380 ms 231552 KB Output is correct
37 Correct 1339 ms 231548 KB Output is correct
38 Correct 60 ms 195012 KB Output is correct
39 Correct 3461 ms 230524 KB Output is correct
40 Correct 769 ms 231552 KB Output is correct
41 Execution timed out 3559 ms 230484 KB Time limit exceeded
42 Halted 0 ms 0 KB -