oj.uz

Submission #1040609

# Submission time Handle Problem Language Result Execution time Memory
1040609 2024-08-01T07:46:20 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 230148 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 = 1800;
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 197068 KB Output is correct
2 Correct 59 ms 197408 KB Output is correct
3 Correct 55 ms 197740 KB Output is correct
4 Correct 56 ms 197592 KB Output is correct
5 Correct 55 ms 197748 KB Output is correct
6 Correct 55 ms 197892 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 197068 KB Output is correct
2 Correct 59 ms 197408 KB Output is correct
3 Correct 55 ms 197740 KB Output is correct
4 Correct 56 ms 197592 KB Output is correct
5 Correct 55 ms 197748 KB Output is correct
6 Correct 55 ms 197892 KB Output is correct
7 Correct 55 ms 197068 KB Output is correct
8 Correct 1169 ms 197340 KB Output is correct
9 Correct 766 ms 197636 KB Output is correct
10 Correct 1123 ms 197600 KB Output is correct
11 Correct 459 ms 197800 KB Output is correct
12 Correct 318 ms 198108 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 197064 KB Output is correct
2 Correct 120 ms 230148 KB Output is correct
3 Correct 115 ms 230144 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 197064 KB Output is correct
2 Correct 120 ms 230148 KB Output is correct
3 Correct 115 ms 230144 KB Output is correct
4 Correct 55 ms 197064 KB Output is correct
5 Correct 723 ms 227472 KB Output is correct
6 Correct 1219 ms 227888 KB Output is correct
7 Correct 1469 ms 227536 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197076 KB Output is correct
2 Correct 139 ms 229120 KB Output is correct
3 Correct 141 ms 229116 KB Output is correct
4 Correct 112 ms 230136 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197076 KB Output is correct
2 Correct 139 ms 229120 KB Output is correct
3 Correct 141 ms 229116 KB Output is correct
4 Correct 112 ms 230136 KB Output is correct
5 Correct 61 ms 197060 KB Output is correct
6 Correct 2722 ms 226328 KB Output is correct
7 Correct 796 ms 227820 KB Output is correct
8 Execution timed out 3579 ms 226292 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 197064 KB Output is correct
2 Correct 103 ms 218628 KB Output is correct
3 Correct 131 ms 217968 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 197064 KB Output is correct
2 Correct 103 ms 218628 KB Output is correct
3 Correct 131 ms 217968 KB Output is correct
4 Correct 54 ms 197164 KB Output is correct
5 Correct 886 ms 215804 KB Output is correct
6 Correct 2243 ms 216580 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197060 KB Output is correct
2 Correct 138 ms 229120 KB Output is correct
3 Correct 135 ms 229124 KB Output is correct
4 Correct 107 ms 230140 KB Output is correct
5 Correct 50 ms 197064 KB Output is correct
6 Correct 101 ms 218628 KB Output is correct
7 Correct 126 ms 217988 KB Output is correct
8 Correct 128 ms 218368 KB Output is correct
9 Correct 133 ms 218388 KB Output is correct
10 Correct 121 ms 223228 KB Output is correct
11 Correct 121 ms 222460 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197060 KB Output is correct
2 Correct 138 ms 229120 KB Output is correct
3 Correct 135 ms 229124 KB Output is correct
4 Correct 107 ms 230140 KB Output is correct
5 Correct 50 ms 197064 KB Output is correct
6 Correct 101 ms 218628 KB Output is correct
7 Correct 126 ms 217988 KB Output is correct
8 Correct 128 ms 218368 KB Output is correct
9 Correct 133 ms 218388 KB Output is correct
10 Correct 121 ms 223228 KB Output is correct
11 Correct 121 ms 222460 KB Output is correct
12 Correct 54 ms 197068 KB Output is correct
13 Correct 2826 ms 226512 KB Output is correct
14 Correct 840 ms 227604 KB Output is correct
15 Execution timed out 3535 ms 226304 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 197064 KB Output is correct
2 Correct 62 ms 197576 KB Output is correct
3 Correct 58 ms 197636 KB Output is correct
4 Correct 66 ms 197592 KB Output is correct
5 Correct 56 ms 197892 KB Output is correct
6 Correct 62 ms 197888 KB Output is correct
7 Correct 51 ms 197064 KB Output is correct
8 Correct 114 ms 230148 KB Output is correct
9 Correct 110 ms 230144 KB Output is correct
10 Correct 55 ms 197064 KB Output is correct
11 Correct 142 ms 229120 KB Output is correct
12 Correct 137 ms 229008 KB Output is correct
13 Correct 101 ms 230144 KB Output is correct
14 Correct 50 ms 197060 KB Output is correct
15 Correct 122 ms 218620 KB Output is correct
16 Correct 133 ms 217956 KB Output is correct
17 Correct 133 ms 218432 KB Output is correct
18 Correct 140 ms 218368 KB Output is correct
19 Correct 129 ms 223236 KB Output is correct
20 Correct 129 ms 222464 KB Output is correct
21 Correct 129 ms 222720 KB Output is correct
22 Correct 126 ms 223232 KB Output is correct
23 Correct 135 ms 219364 KB Output is correct
24 Correct 131 ms 219648 KB Output is correct
25 Correct 123 ms 225072 KB Output is correct
26 Correct 116 ms 218880 KB Output is correct
27 Correct 111 ms 218884 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 197064 KB Output is correct
2 Correct 62 ms 197576 KB Output is correct
3 Correct 58 ms 197636 KB Output is correct
4 Correct 66 ms 197592 KB Output is correct
5 Correct 56 ms 197892 KB Output is correct
6 Correct 62 ms 197888 KB Output is correct
7 Correct 51 ms 197064 KB Output is correct
8 Correct 114 ms 230148 KB Output is correct
9 Correct 110 ms 230144 KB Output is correct
10 Correct 55 ms 197064 KB Output is correct
11 Correct 142 ms 229120 KB Output is correct
12 Correct 137 ms 229008 KB Output is correct
13 Correct 101 ms 230144 KB Output is correct
14 Correct 50 ms 197060 KB Output is correct
15 Correct 122 ms 218620 KB Output is correct
16 Correct 133 ms 217956 KB Output is correct
17 Correct 133 ms 218432 KB Output is correct
18 Correct 140 ms 218368 KB Output is correct
19 Correct 129 ms 223236 KB Output is correct
20 Correct 129 ms 222464 KB Output is correct
21 Correct 129 ms 222720 KB Output is correct
22 Correct 126 ms 223232 KB Output is correct
23 Correct 135 ms 219364 KB Output is correct
24 Correct 131 ms 219648 KB Output is correct
25 Correct 123 ms 225072 KB Output is correct
26 Correct 116 ms 218880 KB Output is correct
27 Correct 111 ms 218884 KB Output is correct
28 Correct 54 ms 197184 KB Output is correct
29 Correct 1176 ms 197372 KB Output is correct
30 Correct 802 ms 197756 KB Output is correct
31 Correct 1229 ms 197648 KB Output is correct
32 Correct 491 ms 197856 KB Output is correct
33 Correct 324 ms 198144 KB Output is correct
34 Correct 82 ms 197164 KB Output is correct
35 Correct 651 ms 227552 KB Output is correct
36 Correct 1120 ms 227840 KB Output is correct
37 Correct 1353 ms 227608 KB Output is correct
38 Correct 59 ms 197180 KB Output is correct
39 Correct 2728 ms 226280 KB Output is correct
40 Correct 836 ms 227568 KB Output is correct
41 Execution timed out 3532 ms 226120 KB Time limit exceeded
42 Halted 0 ms 0 KB -