oj.uz

Submission #1040649

# Submission time Handle Problem Language Result Execution time Memory
1040649 2024-08-01T08:10:22 Z Plurm Inside information (BOI21_servers) C++11
95 / 100
 3500 ms 230400 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 = 1000;
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 54 ms 197320 KB Output is correct
2 Correct 59 ms 197596 KB Output is correct
3 Correct 56 ms 197640 KB Output is correct
4 Correct 59 ms 197596 KB Output is correct
5 Correct 57 ms 197812 KB Output is correct
6 Correct 56 ms 197896 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 197320 KB Output is correct
2 Correct 59 ms 197596 KB Output is correct
3 Correct 56 ms 197640 KB Output is correct
4 Correct 59 ms 197596 KB Output is correct
5 Correct 57 ms 197812 KB Output is correct
6 Correct 56 ms 197896 KB Output is correct
7 Correct 80 ms 197064 KB Output is correct
8 Correct 738 ms 197592 KB Output is correct
9 Correct 438 ms 197640 KB Output is correct
10 Correct 717 ms 197652 KB Output is correct
11 Correct 1065 ms 197748 KB Output is correct
12 Correct 423 ms 198024 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 76 ms 197220 KB Output is correct
2 Correct 121 ms 230144 KB Output is correct
3 Correct 116 ms 230168 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 76 ms 197220 KB Output is correct
2 Correct 121 ms 230144 KB Output is correct
3 Correct 116 ms 230168 KB Output is correct
4 Correct 81 ms 197200 KB Output is correct
5 Correct 857 ms 227580 KB Output is correct
6 Correct 1203 ms 227876 KB Output is correct
7 Correct 1375 ms 227584 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 197096 KB Output is correct
2 Correct 146 ms 229120 KB Output is correct
3 Correct 182 ms 229024 KB Output is correct
4 Correct 117 ms 230148 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 197096 KB Output is correct
2 Correct 146 ms 229120 KB Output is correct
3 Correct 182 ms 229024 KB Output is correct
4 Correct 117 ms 230148 KB Output is correct
5 Correct 57 ms 197060 KB Output is correct
6 Execution timed out 3579 ms 226244 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 196976 KB Output is correct
2 Correct 130 ms 218496 KB Output is correct
3 Correct 139 ms 218112 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 196976 KB Output is correct
2 Correct 130 ms 218496 KB Output is correct
3 Correct 139 ms 218112 KB Output is correct
4 Correct 54 ms 197068 KB Output is correct
5 Correct 928 ms 215680 KB Output is correct
6 Correct 1973 ms 216704 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 197060 KB Output is correct
2 Correct 138 ms 229116 KB Output is correct
3 Correct 142 ms 228948 KB Output is correct
4 Correct 111 ms 230144 KB Output is correct
5 Correct 51 ms 197064 KB Output is correct
6 Correct 102 ms 218628 KB Output is correct
7 Correct 131 ms 218140 KB Output is correct
8 Correct 140 ms 218364 KB Output is correct
9 Correct 135 ms 218464 KB Output is correct
10 Correct 124 ms 223232 KB Output is correct
11 Correct 126 ms 222468 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 197060 KB Output is correct
2 Correct 138 ms 229116 KB Output is correct
3 Correct 142 ms 228948 KB Output is correct
4 Correct 111 ms 230144 KB Output is correct
5 Correct 51 ms 197064 KB Output is correct
6 Correct 102 ms 218628 KB Output is correct
7 Correct 131 ms 218140 KB Output is correct
8 Correct 140 ms 218364 KB Output is correct
9 Correct 135 ms 218464 KB Output is correct
10 Correct 124 ms 223232 KB Output is correct
11 Correct 126 ms 222468 KB Output is correct
12 Correct 55 ms 197112 KB Output is correct
13 Correct 2626 ms 226396 KB Output is correct
14 Correct 725 ms 227584 KB Output is correct
15 Correct 3402 ms 226248 KB Output is correct
16 Correct 3388 ms 228628 KB Output is correct
17 Correct 56 ms 197944 KB Output is correct
18 Correct 759 ms 218800 KB Output is correct
19 Correct 1642 ms 219652 KB Output is correct
20 Correct 2923 ms 218372 KB Output is correct
21 Correct 2449 ms 218624 KB Output is correct
22 Correct 1921 ms 221948 KB Output is correct
23 Correct 1281 ms 224936 KB Output is correct
24 Correct 532 ms 225868 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 197056 KB Output is correct
2 Correct 57 ms 197592 KB Output is correct
3 Correct 58 ms 197632 KB Output is correct
4 Correct 57 ms 197600 KB Output is correct
5 Correct 56 ms 197988 KB Output is correct
6 Correct 54 ms 197892 KB Output is correct
7 Correct 53 ms 197040 KB Output is correct
8 Correct 112 ms 230352 KB Output is correct
9 Correct 113 ms 230144 KB Output is correct
10 Correct 55 ms 197064 KB Output is correct
11 Correct 140 ms 229084 KB Output is correct
12 Correct 138 ms 229004 KB Output is correct
13 Correct 111 ms 230400 KB Output is correct
14 Correct 50 ms 197032 KB Output is correct
15 Correct 102 ms 218652 KB Output is correct
16 Correct 131 ms 218112 KB Output is correct
17 Correct 136 ms 218460 KB Output is correct
18 Correct 134 ms 218368 KB Output is correct
19 Correct 121 ms 223244 KB Output is correct
20 Correct 124 ms 222248 KB Output is correct
21 Correct 123 ms 222820 KB Output is correct
22 Correct 120 ms 223228 KB Output is correct
23 Correct 137 ms 219588 KB Output is correct
24 Correct 140 ms 219652 KB Output is correct
25 Correct 130 ms 225024 KB Output is correct
26 Correct 121 ms 218732 KB Output is correct
27 Correct 117 ms 219400 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 197056 KB Output is correct
2 Correct 57 ms 197592 KB Output is correct
3 Correct 58 ms 197632 KB Output is correct
4 Correct 57 ms 197600 KB Output is correct
5 Correct 56 ms 197988 KB Output is correct
6 Correct 54 ms 197892 KB Output is correct
7 Correct 53 ms 197040 KB Output is correct
8 Correct 112 ms 230352 KB Output is correct
9 Correct 113 ms 230144 KB Output is correct
10 Correct 55 ms 197064 KB Output is correct
11 Correct 140 ms 229084 KB Output is correct
12 Correct 138 ms 229004 KB Output is correct
13 Correct 111 ms 230400 KB Output is correct
14 Correct 50 ms 197032 KB Output is correct
15 Correct 102 ms 218652 KB Output is correct
16 Correct 131 ms 218112 KB Output is correct
17 Correct 136 ms 218460 KB Output is correct
18 Correct 134 ms 218368 KB Output is correct
19 Correct 121 ms 223244 KB Output is correct
20 Correct 124 ms 222248 KB Output is correct
21 Correct 123 ms 222820 KB Output is correct
22 Correct 120 ms 223228 KB Output is correct
23 Correct 137 ms 219588 KB Output is correct
24 Correct 140 ms 219652 KB Output is correct
25 Correct 130 ms 225024 KB Output is correct
26 Correct 121 ms 218732 KB Output is correct
27 Correct 117 ms 219400 KB Output is correct
28 Correct 53 ms 197172 KB Output is correct
29 Correct 705 ms 197464 KB Output is correct
30 Correct 408 ms 197636 KB Output is correct
31 Correct 655 ms 197600 KB Output is correct
32 Correct 1077 ms 198056 KB Output is correct
33 Correct 399 ms 198144 KB Output is correct
34 Correct 52 ms 197060 KB Output is correct
35 Correct 739 ms 227588 KB Output is correct
36 Correct 998 ms 227924 KB Output is correct
37 Correct 1109 ms 227584 KB Output is correct
38 Correct 56 ms 197068 KB Output is correct
39 Correct 2600 ms 226284 KB Output is correct
40 Correct 670 ms 227628 KB Output is correct
41 Correct 3442 ms 225980 KB Output is correct
42 Correct 3311 ms 226044 KB Output is correct
43 Correct 55 ms 197832 KB Output is correct
44 Correct 791 ms 218712 KB Output is correct
45 Correct 1555 ms 219488 KB Output is correct
46 Correct 2829 ms 218368 KB Output is correct
47 Correct 2444 ms 218648 KB Output is correct
48 Correct 2231 ms 222096 KB Output is correct
49 Correct 1498 ms 224856 KB Output is correct
50 Correct 604 ms 225796 KB Output is correct
51 Correct 1175 ms 228864 KB Output is correct
52 Correct 898 ms 225788 KB Output is correct
53 Correct 1154 ms 226816 KB Output is correct
54 Correct 879 ms 225964 KB Output is correct
55 Correct 1577 ms 227616 KB Output is correct
56 Correct 2662 ms 219580 KB Output is correct
57 Correct 2708 ms 226204 KB Output is correct
58 Correct 1741 ms 220912 KB Output is correct
59 Correct 280 ms 222412 KB Output is correct