oj.uz

Submission #1040598

# Submission time Handle Problem Language Result Execution time Memory
1040598 2024-08-01T07:44:00 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 230624 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 = 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[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 50 ms 197068 KB Output is correct
2 Correct 61 ms 197492 KB Output is correct
3 Correct 60 ms 197776 KB Output is correct
4 Correct 65 ms 197592 KB Output is correct
5 Correct 65 ms 197964 KB Output is correct
6 Correct 58 ms 197892 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197068 KB Output is correct
2 Correct 61 ms 197492 KB Output is correct
3 Correct 60 ms 197776 KB Output is correct
4 Correct 65 ms 197592 KB Output is correct
5 Correct 65 ms 197964 KB Output is correct
6 Correct 58 ms 197892 KB Output is correct
7 Correct 62 ms 197076 KB Output is correct
8 Correct 1486 ms 197504 KB Output is correct
9 Correct 852 ms 197804 KB Output is correct
10 Correct 1494 ms 197440 KB Output is correct
11 Correct 2135 ms 197740 KB Output is correct
12 Correct 871 ms 198104 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 197072 KB Output is correct
2 Correct 152 ms 230144 KB Output is correct
3 Correct 122 ms 230364 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 197072 KB Output is correct
2 Correct 152 ms 230144 KB Output is correct
3 Correct 122 ms 230364 KB Output is correct
4 Correct 59 ms 197116 KB Output is correct
5 Correct 689 ms 227640 KB Output is correct
6 Correct 1252 ms 227736 KB Output is correct
7 Correct 1721 ms 227588 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 197124 KB Output is correct
2 Correct 164 ms 228972 KB Output is correct
3 Correct 164 ms 229132 KB Output is correct
4 Correct 115 ms 230244 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 197124 KB Output is correct
2 Correct 164 ms 228972 KB Output is correct
3 Correct 164 ms 229132 KB Output is correct
4 Correct 115 ms 230244 KB Output is correct
5 Correct 61 ms 197064 KB Output is correct
6 Execution timed out 3561 ms 226128 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 197060 KB Output is correct
2 Correct 114 ms 218816 KB Output is correct
3 Correct 157 ms 218108 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 197060 KB Output is correct
2 Correct 114 ms 218816 KB Output is correct
3 Correct 157 ms 218108 KB Output is correct
4 Correct 58 ms 197012 KB Output is correct
5 Correct 1329 ms 215888 KB Output is correct
6 Correct 2761 ms 216664 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 197048 KB Output is correct
2 Correct 177 ms 228912 KB Output is correct
3 Correct 170 ms 229124 KB Output is correct
4 Correct 120 ms 230188 KB Output is correct
5 Correct 58 ms 197064 KB Output is correct
6 Correct 117 ms 218624 KB Output is correct
7 Correct 174 ms 218116 KB Output is correct
8 Correct 157 ms 218372 KB Output is correct
9 Correct 162 ms 218308 KB Output is correct
10 Correct 168 ms 223184 KB Output is correct
11 Correct 167 ms 222456 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 197048 KB Output is correct
2 Correct 177 ms 228912 KB Output is correct
3 Correct 170 ms 229124 KB Output is correct
4 Correct 120 ms 230188 KB Output is correct
5 Correct 58 ms 197064 KB Output is correct
6 Correct 117 ms 218624 KB Output is correct
7 Correct 174 ms 218116 KB Output is correct
8 Correct 157 ms 218372 KB Output is correct
9 Correct 162 ms 218308 KB Output is correct
10 Correct 168 ms 223184 KB Output is correct
11 Correct 167 ms 222456 KB Output is correct
12 Correct 71 ms 197064 KB Output is correct
13 Correct 3391 ms 226172 KB Output is correct
14 Correct 871 ms 230624 KB Output is correct
15 Execution timed out 3568 ms 228608 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 197064 KB Output is correct
2 Correct 57 ms 197472 KB Output is correct
3 Correct 58 ms 197636 KB Output is correct
4 Correct 58 ms 197596 KB Output is correct
5 Correct 58 ms 197888 KB Output is correct
6 Correct 56 ms 197896 KB Output is correct
7 Correct 57 ms 197096 KB Output is correct
8 Correct 117 ms 230164 KB Output is correct
9 Correct 114 ms 230144 KB Output is correct
10 Correct 52 ms 197064 KB Output is correct
11 Correct 140 ms 229072 KB Output is correct
12 Correct 130 ms 229084 KB Output is correct
13 Correct 103 ms 230400 KB Output is correct
14 Correct 50 ms 197076 KB Output is correct
15 Correct 105 ms 218468 KB Output is correct
16 Correct 127 ms 218116 KB Output is correct
17 Correct 128 ms 218372 KB Output is correct
18 Correct 130 ms 218368 KB Output is correct
19 Correct 124 ms 223268 KB Output is correct
20 Correct 123 ms 222460 KB Output is correct
21 Correct 117 ms 222744 KB Output is correct
22 Correct 115 ms 223232 KB Output is correct
23 Correct 154 ms 219452 KB Output is correct
24 Correct 133 ms 219572 KB Output is correct
25 Correct 125 ms 225104 KB Output is correct
26 Correct 120 ms 218844 KB Output is correct
27 Correct 131 ms 218876 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 197064 KB Output is correct
2 Correct 57 ms 197472 KB Output is correct
3 Correct 58 ms 197636 KB Output is correct
4 Correct 58 ms 197596 KB Output is correct
5 Correct 58 ms 197888 KB Output is correct
6 Correct 56 ms 197896 KB Output is correct
7 Correct 57 ms 197096 KB Output is correct
8 Correct 117 ms 230164 KB Output is correct
9 Correct 114 ms 230144 KB Output is correct
10 Correct 52 ms 197064 KB Output is correct
11 Correct 140 ms 229072 KB Output is correct
12 Correct 130 ms 229084 KB Output is correct
13 Correct 103 ms 230400 KB Output is correct
14 Correct 50 ms 197076 KB Output is correct
15 Correct 105 ms 218468 KB Output is correct
16 Correct 127 ms 218116 KB Output is correct
17 Correct 128 ms 218372 KB Output is correct
18 Correct 130 ms 218368 KB Output is correct
19 Correct 124 ms 223268 KB Output is correct
20 Correct 123 ms 222460 KB Output is correct
21 Correct 117 ms 222744 KB Output is correct
22 Correct 115 ms 223232 KB Output is correct
23 Correct 154 ms 219452 KB Output is correct
24 Correct 133 ms 219572 KB Output is correct
25 Correct 125 ms 225104 KB Output is correct
26 Correct 120 ms 218844 KB Output is correct
27 Correct 131 ms 218876 KB Output is correct
28 Correct 53 ms 197184 KB Output is correct
29 Correct 1405 ms 197340 KB Output is correct
30 Correct 771 ms 197640 KB Output is correct
31 Correct 1380 ms 197600 KB Output is correct
32 Correct 2033 ms 197720 KB Output is correct
33 Correct 800 ms 198072 KB Output is correct
34 Correct 53 ms 197068 KB Output is correct
35 Correct 652 ms 227516 KB Output is correct
36 Correct 1129 ms 227844 KB Output is correct
37 Correct 1450 ms 227540 KB Output is correct
38 Correct 57 ms 197068 KB Output is correct
39 Correct 3109 ms 226200 KB Output is correct
40 Correct 1025 ms 227520 KB Output is correct
41 Execution timed out 3579 ms 226160 KB Time limit exceeded
42 Halted 0 ms 0 KB -