oj.uz

Submission #1040573

# Submission time Handle Problem Language Result Execution time Memory
1040573 2024-08-01T07:34:42 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 239708 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;
}
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;
        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]);
                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 51 ms 197064 KB Output is correct
2 Correct 58 ms 197852 KB Output is correct
3 Correct 55 ms 197892 KB Output is correct
4 Correct 58 ms 197848 KB Output is correct
5 Correct 62 ms 198400 KB Output is correct
6 Correct 63 ms 198144 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 197064 KB Output is correct
2 Correct 58 ms 197852 KB Output is correct
3 Correct 55 ms 197892 KB Output is correct
4 Correct 58 ms 197848 KB Output is correct
5 Correct 62 ms 198400 KB Output is correct
6 Correct 63 ms 198144 KB Output is correct
7 Correct 58 ms 197080 KB Output is correct
8 Correct 393 ms 197636 KB Output is correct
9 Correct 236 ms 197868 KB Output is correct
10 Correct 278 ms 197480 KB Output is correct
11 Correct 181 ms 197892 KB Output is correct
12 Correct 186 ms 197896 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197064 KB Output is correct
2 Correct 299 ms 236544 KB Output is correct
3 Correct 298 ms 236412 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197064 KB Output is correct
2 Correct 299 ms 236544 KB Output is correct
3 Correct 298 ms 236412 KB Output is correct
4 Correct 53 ms 197064 KB Output is correct
5 Correct 1464 ms 227596 KB Output is correct
6 Correct 1651 ms 227824 KB Output is correct
7 Correct 1667 ms 227580 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 197112 KB Output is correct
2 Correct 207 ms 235136 KB Output is correct
3 Correct 202 ms 235532 KB Output is correct
4 Correct 1157 ms 236452 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 197112 KB Output is correct
2 Correct 207 ms 235136 KB Output is correct
3 Correct 202 ms 235532 KB Output is correct
4 Correct 1157 ms 236452 KB Output is correct
5 Correct 54 ms 197064 KB Output is correct
6 Execution timed out 3539 ms 226056 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197064 KB Output is correct
2 Correct 124 ms 224640 KB Output is correct
3 Correct 243 ms 224176 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197064 KB Output is correct
2 Correct 124 ms 224640 KB Output is correct
3 Correct 243 ms 224176 KB Output is correct
4 Correct 57 ms 197064 KB Output is correct
5 Correct 1099 ms 215804 KB Output is correct
6 Correct 2397 ms 224100 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 197104 KB Output is correct
2 Correct 192 ms 235280 KB Output is correct
3 Correct 260 ms 235144 KB Output is correct
4 Correct 1137 ms 236444 KB Output is correct
5 Correct 53 ms 197140 KB Output is correct
6 Correct 141 ms 224784 KB Output is correct
7 Correct 251 ms 224056 KB Output is correct
8 Correct 216 ms 224380 KB Output is correct
9 Correct 360 ms 224576 KB Output is correct
10 Correct 191 ms 229252 KB Output is correct
11 Correct 141 ms 228480 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 197104 KB Output is correct
2 Correct 192 ms 235280 KB Output is correct
3 Correct 260 ms 235144 KB Output is correct
4 Correct 1137 ms 236444 KB Output is correct
5 Correct 53 ms 197140 KB Output is correct
6 Correct 141 ms 224784 KB Output is correct
7 Correct 251 ms 224056 KB Output is correct
8 Correct 216 ms 224380 KB Output is correct
9 Correct 360 ms 224576 KB Output is correct
10 Correct 191 ms 229252 KB Output is correct
11 Correct 141 ms 228480 KB Output is correct
12 Correct 54 ms 197068 KB Output is correct
13 Execution timed out 3555 ms 228100 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 198088 KB Output is correct
2 Correct 85 ms 199104 KB Output is correct
3 Correct 93 ms 199256 KB Output is correct
4 Correct 61 ms 199388 KB Output is correct
5 Correct 61 ms 199640 KB Output is correct
6 Correct 59 ms 199680 KB Output is correct
7 Correct 53 ms 198084 KB Output is correct
8 Correct 305 ms 239232 KB Output is correct
9 Correct 303 ms 239488 KB Output is correct
10 Correct 55 ms 197980 KB Output is correct
11 Correct 204 ms 238460 KB Output is correct
12 Correct 199 ms 238608 KB Output is correct
13 Correct 1122 ms 239708 KB Output is correct
14 Correct 53 ms 198080 KB Output is correct
15 Correct 126 ms 227976 KB Output is correct
16 Correct 230 ms 227200 KB Output is correct
17 Correct 191 ms 227776 KB Output is correct
18 Correct 346 ms 227968 KB Output is correct
19 Correct 165 ms 232580 KB Output is correct
20 Correct 144 ms 231804 KB Output is correct
21 Correct 325 ms 232368 KB Output is correct
22 Correct 318 ms 232776 KB Output is correct
23 Correct 328 ms 228900 KB Output is correct
24 Correct 367 ms 229172 KB Output is correct
25 Correct 294 ms 234488 KB Output is correct
26 Correct 221 ms 228176 KB Output is correct
27 Correct 179 ms 228228 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 198088 KB Output is correct
2 Correct 85 ms 199104 KB Output is correct
3 Correct 93 ms 199256 KB Output is correct
4 Correct 61 ms 199388 KB Output is correct
5 Correct 61 ms 199640 KB Output is correct
6 Correct 59 ms 199680 KB Output is correct
7 Correct 53 ms 198084 KB Output is correct
8 Correct 305 ms 239232 KB Output is correct
9 Correct 303 ms 239488 KB Output is correct
10 Correct 55 ms 197980 KB Output is correct
11 Correct 204 ms 238460 KB Output is correct
12 Correct 199 ms 238608 KB Output is correct
13 Correct 1122 ms 239708 KB Output is correct
14 Correct 53 ms 198080 KB Output is correct
15 Correct 126 ms 227976 KB Output is correct
16 Correct 230 ms 227200 KB Output is correct
17 Correct 191 ms 227776 KB Output is correct
18 Correct 346 ms 227968 KB Output is correct
19 Correct 165 ms 232580 KB Output is correct
20 Correct 144 ms 231804 KB Output is correct
21 Correct 325 ms 232368 KB Output is correct
22 Correct 318 ms 232776 KB Output is correct
23 Correct 328 ms 228900 KB Output is correct
24 Correct 367 ms 229172 KB Output is correct
25 Correct 294 ms 234488 KB Output is correct
26 Correct 221 ms 228176 KB Output is correct
27 Correct 179 ms 228228 KB Output is correct
28 Correct 69 ms 197896 KB Output is correct
29 Correct 368 ms 198684 KB Output is correct
30 Correct 251 ms 199116 KB Output is correct
31 Correct 309 ms 198772 KB Output is correct
32 Correct 200 ms 198916 KB Output is correct
33 Correct 189 ms 199152 KB Output is correct
34 Correct 54 ms 198088 KB Output is correct
35 Correct 1709 ms 230652 KB Output is correct
36 Correct 2230 ms 227832 KB Output is correct
37 Correct 2188 ms 227656 KB Output is correct
38 Correct 55 ms 196980 KB Output is correct
39 Execution timed out 3550 ms 226056 KB Time limit exceeded
40 Halted 0 ms 0 KB -