oj.uz

Submission #1040654

# Submission time Handle Problem Language Result Execution time Memory
1040654 2024-08-01T08:12:25 Z Plurm Inside information (BOI21_servers) C++11
70 / 100
 3500 ms 230660 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 = 900;
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 56 ms 197064 KB Output is correct
2 Correct 57 ms 197592 KB Output is correct
3 Correct 57 ms 197632 KB Output is correct
4 Correct 57 ms 197592 KB Output is correct
5 Correct 67 ms 197788 KB Output is correct
6 Correct 55 ms 197896 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 197064 KB Output is correct
2 Correct 57 ms 197592 KB Output is correct
3 Correct 57 ms 197632 KB Output is correct
4 Correct 57 ms 197592 KB Output is correct
5 Correct 67 ms 197788 KB Output is correct
6 Correct 55 ms 197896 KB Output is correct
7 Correct 54 ms 197060 KB Output is correct
8 Correct 601 ms 197600 KB Output is correct
9 Correct 415 ms 197632 KB Output is correct
10 Correct 584 ms 197668 KB Output is correct
11 Correct 444 ms 197896 KB Output is correct
12 Correct 236 ms 197916 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197060 KB Output is correct
2 Correct 120 ms 230300 KB Output is correct
3 Correct 114 ms 230144 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197060 KB Output is correct
2 Correct 120 ms 230300 KB Output is correct
3 Correct 114 ms 230144 KB Output is correct
4 Correct 56 ms 197064 KB Output is correct
5 Correct 815 ms 227552 KB Output is correct
6 Correct 971 ms 227872 KB Output is correct
7 Correct 1097 ms 227836 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 197060 KB Output is correct
2 Correct 147 ms 229112 KB Output is correct
3 Correct 141 ms 229332 KB Output is correct
4 Correct 108 ms 230144 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 197060 KB Output is correct
2 Correct 147 ms 229112 KB Output is correct
3 Correct 141 ms 229332 KB Output is correct
4 Correct 108 ms 230144 KB Output is correct
5 Correct 58 ms 197060 KB Output is correct
6 Correct 2840 ms 226100 KB Output is correct
7 Correct 654 ms 230660 KB Output is correct
8 Correct 3312 ms 228932 KB Output is correct
9 Correct 3326 ms 228888 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 197064 KB Output is correct
2 Correct 103 ms 218624 KB Output is correct
3 Correct 136 ms 217992 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 103 ms 218624 KB Output is correct
3 Correct 136 ms 217992 KB Output is correct
4 Correct 54 ms 197064 KB Output is correct
5 Correct 600 ms 215916 KB Output is correct
6 Correct 1516 ms 216896 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 197040 KB Output is correct
2 Correct 141 ms 229132 KB Output is correct
3 Correct 146 ms 229112 KB Output is correct
4 Correct 104 ms 230148 KB Output is correct
5 Correct 49 ms 197120 KB Output is correct
6 Correct 105 ms 218552 KB Output is correct
7 Correct 133 ms 218108 KB Output is correct
8 Correct 132 ms 218556 KB Output is correct
9 Correct 137 ms 218392 KB Output is correct
10 Correct 122 ms 223232 KB Output is correct
11 Correct 120 ms 222364 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 197040 KB Output is correct
2 Correct 141 ms 229132 KB Output is correct
3 Correct 146 ms 229112 KB Output is correct
4 Correct 104 ms 230148 KB Output is correct
5 Correct 49 ms 197120 KB Output is correct
6 Correct 105 ms 218552 KB Output is correct
7 Correct 133 ms 218108 KB Output is correct
8 Correct 132 ms 218556 KB Output is correct
9 Correct 137 ms 218392 KB Output is correct
10 Correct 122 ms 223232 KB Output is correct
11 Correct 120 ms 222364 KB Output is correct
12 Correct 54 ms 197180 KB Output is correct
13 Correct 2698 ms 226056 KB Output is correct
14 Correct 651 ms 227584 KB Output is correct
15 Correct 3486 ms 226044 KB Output is correct
16 Execution timed out 3545 ms 226068 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 197060 KB Output is correct
2 Correct 60 ms 197560 KB Output is correct
3 Correct 55 ms 197636 KB Output is correct
4 Correct 59 ms 197652 KB Output is correct
5 Correct 63 ms 197892 KB Output is correct
6 Correct 60 ms 198096 KB Output is correct
7 Correct 60 ms 197036 KB Output is correct
8 Correct 133 ms 230180 KB Output is correct
9 Correct 125 ms 230152 KB Output is correct
10 Correct 52 ms 197068 KB Output is correct
11 Correct 171 ms 228920 KB Output is correct
12 Correct 155 ms 229124 KB Output is correct
13 Correct 122 ms 230148 KB Output is correct
14 Correct 58 ms 197064 KB Output is correct
15 Correct 118 ms 218564 KB Output is correct
16 Correct 165 ms 218128 KB Output is correct
17 Correct 151 ms 218392 KB Output is correct
18 Correct 149 ms 218368 KB Output is correct
19 Correct 136 ms 223112 KB Output is correct
20 Correct 129 ms 222464 KB Output is correct
21 Correct 133 ms 222732 KB Output is correct
22 Correct 124 ms 223492 KB Output is correct
23 Correct 151 ms 219452 KB Output is correct
24 Correct 183 ms 219648 KB Output is correct
25 Correct 162 ms 225024 KB Output is correct
26 Correct 128 ms 218820 KB Output is correct
27 Correct 125 ms 219108 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 197060 KB Output is correct
2 Correct 60 ms 197560 KB Output is correct
3 Correct 55 ms 197636 KB Output is correct
4 Correct 59 ms 197652 KB Output is correct
5 Correct 63 ms 197892 KB Output is correct
6 Correct 60 ms 198096 KB Output is correct
7 Correct 60 ms 197036 KB Output is correct
8 Correct 133 ms 230180 KB Output is correct
9 Correct 125 ms 230152 KB Output is correct
10 Correct 52 ms 197068 KB Output is correct
11 Correct 171 ms 228920 KB Output is correct
12 Correct 155 ms 229124 KB Output is correct
13 Correct 122 ms 230148 KB Output is correct
14 Correct 58 ms 197064 KB Output is correct
15 Correct 118 ms 218564 KB Output is correct
16 Correct 165 ms 218128 KB Output is correct
17 Correct 151 ms 218392 KB Output is correct
18 Correct 149 ms 218368 KB Output is correct
19 Correct 136 ms 223112 KB Output is correct
20 Correct 129 ms 222464 KB Output is correct
21 Correct 133 ms 222732 KB Output is correct
22 Correct 124 ms 223492 KB Output is correct
23 Correct 151 ms 219452 KB Output is correct
24 Correct 183 ms 219648 KB Output is correct
25 Correct 162 ms 225024 KB Output is correct
26 Correct 128 ms 218820 KB Output is correct
27 Correct 125 ms 219108 KB Output is correct
28 Correct 76 ms 197064 KB Output is correct
29 Correct 670 ms 197604 KB Output is correct
30 Correct 381 ms 197636 KB Output is correct
31 Correct 597 ms 197604 KB Output is correct
32 Correct 453 ms 197840 KB Output is correct
33 Correct 255 ms 198076 KB Output is correct
34 Correct 63 ms 197064 KB Output is correct
35 Correct 917 ms 227388 KB Output is correct
36 Correct 1171 ms 227868 KB Output is correct
37 Correct 1344 ms 227592 KB Output is correct
38 Correct 56 ms 197132 KB Output is correct
39 Execution timed out 3544 ms 226204 KB Time limit exceeded
40 Halted 0 ms 0 KB -