oj.uz

Submission #1040590

# Submission time Handle Problem Language Result Execution time Memory
1040590 2024-08-01T07:42:28 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 233728 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(const int& u, const int& v){
    if(st[u] > st[v]) return rmq(st[v], st[u]).second;
    else return rmq(st[u], st[v]).second;
}
inline bool search(const int& a, const 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<tuple<int,int,int>> buffer;
const int THRESH = 1200;
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[get<0>(p)]--;
            evp[get<1>(p)]--;
            evp[get<2>(p)] += 2;
        }
        update(1);
        for(auto p : buffer){
            evp[get<0>(p)]++;
            evp[get<1>(p)]++;
            evp[get<2>(p)] -= 2;
        }
        buffer.clear();
    }
    int ret = qs[d];
    for(auto p : buffer){
        if(search(get<0>(p), d) || search(get<1>(p), d)){
            ret++;
        }else if(search(get<2>(p), d)){
            ret += 2;
        }
    }
    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;
        qs[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]);
                last++;
                buffer.push_back({ids[a], ids[b], last});
                ids[a] = ids[b] = last;
                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 55 ms 198048 KB Output is correct
2 Correct 63 ms 198776 KB Output is correct
3 Correct 61 ms 199092 KB Output is correct
4 Correct 82 ms 199128 KB Output is correct
5 Correct 59 ms 199284 KB Output is correct
6 Correct 59 ms 199424 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 198048 KB Output is correct
2 Correct 63 ms 198776 KB Output is correct
3 Correct 61 ms 199092 KB Output is correct
4 Correct 82 ms 199128 KB Output is correct
5 Correct 59 ms 199284 KB Output is correct
6 Correct 59 ms 199424 KB Output is correct
7 Correct 59 ms 198056 KB Output is correct
8 Correct 812 ms 198616 KB Output is correct
9 Correct 520 ms 198656 KB Output is correct
10 Correct 778 ms 198880 KB Output is correct
11 Correct 512 ms 198916 KB Output is correct
12 Correct 292 ms 199144 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 197880 KB Output is correct
2 Correct 127 ms 233220 KB Output is correct
3 Correct 153 ms 233048 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 197880 KB Output is correct
2 Correct 127 ms 233220 KB Output is correct
3 Correct 153 ms 233048 KB Output is correct
4 Correct 56 ms 198092 KB Output is correct
5 Correct 813 ms 230380 KB Output is correct
6 Correct 1110 ms 229484 KB Output is correct
7 Correct 1395 ms 229664 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 198092 KB Output is correct
2 Correct 160 ms 232448 KB Output is correct
3 Correct 171 ms 232444 KB Output is correct
4 Correct 123 ms 233376 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 198092 KB Output is correct
2 Correct 160 ms 232448 KB Output is correct
3 Correct 171 ms 232444 KB Output is correct
4 Correct 123 ms 233376 KB Output is correct
5 Correct 58 ms 197828 KB Output is correct
6 Execution timed out 3594 ms 229128 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 198088 KB Output is correct
2 Correct 115 ms 221960 KB Output is correct
3 Correct 173 ms 221184 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 198088 KB Output is correct
2 Correct 115 ms 221960 KB Output is correct
3 Correct 173 ms 221184 KB Output is correct
4 Correct 66 ms 197876 KB Output is correct
5 Correct 1107 ms 218832 KB Output is correct
6 Correct 2389 ms 219648 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 198000 KB Output is correct
2 Correct 170 ms 232448 KB Output is correct
3 Correct 165 ms 232248 KB Output is correct
4 Correct 117 ms 233728 KB Output is correct
5 Correct 54 ms 197932 KB Output is correct
6 Correct 111 ms 221764 KB Output is correct
7 Correct 150 ms 221180 KB Output is correct
8 Correct 157 ms 221696 KB Output is correct
9 Correct 213 ms 221696 KB Output is correct
10 Correct 133 ms 226556 KB Output is correct
11 Correct 130 ms 225796 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 198000 KB Output is correct
2 Correct 170 ms 232448 KB Output is correct
3 Correct 165 ms 232248 KB Output is correct
4 Correct 117 ms 233728 KB Output is correct
5 Correct 54 ms 197932 KB Output is correct
6 Correct 111 ms 221764 KB Output is correct
7 Correct 150 ms 221180 KB Output is correct
8 Correct 157 ms 221696 KB Output is correct
9 Correct 213 ms 221696 KB Output is correct
10 Correct 133 ms 226556 KB Output is correct
11 Correct 130 ms 225796 KB Output is correct
12 Correct 59 ms 197968 KB Output is correct
13 Execution timed out 3564 ms 227420 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 197064 KB Output is correct
2 Correct 62 ms 197616 KB Output is correct
3 Correct 59 ms 197636 KB Output is correct
4 Correct 96 ms 197592 KB Output is correct
5 Correct 60 ms 197792 KB Output is correct
6 Correct 57 ms 197888 KB Output is correct
7 Correct 59 ms 197096 KB Output is correct
8 Correct 159 ms 230144 KB Output is correct
9 Correct 192 ms 230268 KB Output is correct
10 Correct 56 ms 197064 KB Output is correct
11 Correct 159 ms 229004 KB Output is correct
12 Correct 166 ms 229120 KB Output is correct
13 Correct 116 ms 230312 KB Output is correct
14 Correct 66 ms 197068 KB Output is correct
15 Correct 121 ms 218620 KB Output is correct
16 Correct 198 ms 218112 KB Output is correct
17 Correct 179 ms 218280 KB Output is correct
18 Correct 191 ms 218368 KB Output is correct
19 Correct 168 ms 223352 KB Output is correct
20 Correct 134 ms 222408 KB Output is correct
21 Correct 125 ms 222868 KB Output is correct
22 Correct 134 ms 223216 KB Output is correct
23 Correct 152 ms 219392 KB Output is correct
24 Correct 157 ms 219644 KB Output is correct
25 Correct 151 ms 225108 KB Output is correct
26 Correct 134 ms 218880 KB Output is correct
27 Correct 131 ms 218880 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 197064 KB Output is correct
2 Correct 62 ms 197616 KB Output is correct
3 Correct 59 ms 197636 KB Output is correct
4 Correct 96 ms 197592 KB Output is correct
5 Correct 60 ms 197792 KB Output is correct
6 Correct 57 ms 197888 KB Output is correct
7 Correct 59 ms 197096 KB Output is correct
8 Correct 159 ms 230144 KB Output is correct
9 Correct 192 ms 230268 KB Output is correct
10 Correct 56 ms 197064 KB Output is correct
11 Correct 159 ms 229004 KB Output is correct
12 Correct 166 ms 229120 KB Output is correct
13 Correct 116 ms 230312 KB Output is correct
14 Correct 66 ms 197068 KB Output is correct
15 Correct 121 ms 218620 KB Output is correct
16 Correct 198 ms 218112 KB Output is correct
17 Correct 179 ms 218280 KB Output is correct
18 Correct 191 ms 218368 KB Output is correct
19 Correct 168 ms 223352 KB Output is correct
20 Correct 134 ms 222408 KB Output is correct
21 Correct 125 ms 222868 KB Output is correct
22 Correct 134 ms 223216 KB Output is correct
23 Correct 152 ms 219392 KB Output is correct
24 Correct 157 ms 219644 KB Output is correct
25 Correct 151 ms 225108 KB Output is correct
26 Correct 134 ms 218880 KB Output is correct
27 Correct 131 ms 218880 KB Output is correct
28 Correct 58 ms 197068 KB Output is correct
29 Correct 839 ms 197344 KB Output is correct
30 Correct 534 ms 197640 KB Output is correct
31 Correct 765 ms 197828 KB Output is correct
32 Correct 445 ms 197752 KB Output is correct
33 Correct 253 ms 197976 KB Output is correct
34 Correct 59 ms 197060 KB Output is correct
35 Correct 693 ms 227452 KB Output is correct
36 Correct 996 ms 229636 KB Output is correct
37 Correct 1114 ms 229636 KB Output is correct
38 Correct 58 ms 197832 KB Output is correct
39 Correct 2684 ms 229216 KB Output is correct
40 Correct 668 ms 230656 KB Output is correct
41 Correct 3467 ms 228864 KB Output is correct
42 Execution timed out 3578 ms 228860 KB Time limit exceeded
43 Halted 0 ms 0 KB -