oj.uz

Submission #1040552

# Submission time Handle Problem Language Result Execution time Memory
1040552 2024-08-01T07:18:54 Z Plurm Inside information (BOI21_servers) C++11
65 / 100
 3500 ms 236800 KB 
#include <bits/stdc++.h>
using namespace std;

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(int u, int v){
    if(st[u] > st[v]) swap(u, v);
    return rmq(st[u], st[v]).second;
}
inline bool search(int a, 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;
}
map<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;
        buffer[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 195012 KB Output is correct
2 Correct 59 ms 195800 KB Output is correct
3 Correct 56 ms 195844 KB Output is correct
4 Correct 75 ms 195800 KB Output is correct
5 Correct 59 ms 196096 KB Output is correct
6 Correct 56 ms 196096 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 195012 KB Output is correct
2 Correct 59 ms 195800 KB Output is correct
3 Correct 56 ms 195844 KB Output is correct
4 Correct 75 ms 195800 KB Output is correct
5 Correct 59 ms 196096 KB Output is correct
6 Correct 56 ms 196096 KB Output is correct
7 Correct 54 ms 195024 KB Output is correct
8 Correct 404 ms 197492 KB Output is correct
9 Correct 215 ms 197892 KB Output is correct
10 Correct 288 ms 197608 KB Output is correct
11 Correct 204 ms 198020 KB Output is correct
12 Correct 242 ms 198120 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 195012 KB Output is correct
2 Correct 186 ms 236544 KB Output is correct
3 Correct 194 ms 236544 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 195012 KB Output is correct
2 Correct 186 ms 236544 KB Output is correct
3 Correct 194 ms 236544 KB Output is correct
4 Correct 55 ms 195016 KB Output is correct
5 Correct 1512 ms 233076 KB Output is correct
6 Correct 1762 ms 233468 KB Output is correct
7 Correct 1732 ms 233336 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 195096 KB Output is correct
2 Correct 237 ms 235364 KB Output is correct
3 Correct 224 ms 235268 KB Output is correct
4 Correct 148 ms 236800 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 195096 KB Output is correct
2 Correct 237 ms 235364 KB Output is correct
3 Correct 224 ms 235268 KB Output is correct
4 Correct 148 ms 236800 KB Output is correct
5 Correct 53 ms 195016 KB Output is correct
6 Execution timed out 3525 ms 231676 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 195016 KB Output is correct
2 Correct 148 ms 224908 KB Output is correct
3 Correct 219 ms 224284 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 195016 KB Output is correct
2 Correct 148 ms 224908 KB Output is correct
3 Correct 219 ms 224284 KB Output is correct
4 Correct 54 ms 195016 KB Output is correct
5 Correct 1174 ms 221488 KB Output is correct
6 Correct 2317 ms 223632 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 195016 KB Output is correct
2 Correct 230 ms 235528 KB Output is correct
3 Correct 215 ms 235268 KB Output is correct
4 Correct 150 ms 236544 KB Output is correct
5 Correct 51 ms 195044 KB Output is correct
6 Correct 157 ms 224768 KB Output is correct
7 Correct 211 ms 224168 KB Output is correct
8 Correct 201 ms 224508 KB Output is correct
9 Correct 223 ms 224624 KB Output is correct
10 Correct 181 ms 229376 KB Output is correct
11 Correct 190 ms 228612 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 195016 KB Output is correct
2 Correct 230 ms 235528 KB Output is correct
3 Correct 215 ms 235268 KB Output is correct
4 Correct 150 ms 236544 KB Output is correct
5 Correct 51 ms 195044 KB Output is correct
6 Correct 157 ms 224768 KB Output is correct
7 Correct 211 ms 224168 KB Output is correct
8 Correct 201 ms 224508 KB Output is correct
9 Correct 223 ms 224624 KB Output is correct
10 Correct 181 ms 229376 KB Output is correct
11 Correct 190 ms 228612 KB Output is correct
12 Correct 72 ms 195020 KB Output is correct
13 Execution timed out 3578 ms 231644 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 195012 KB Output is correct
2 Correct 57 ms 195804 KB Output is correct
3 Correct 57 ms 195852 KB Output is correct
4 Correct 60 ms 195788 KB Output is correct
5 Correct 60 ms 196060 KB Output is correct
6 Correct 55 ms 196100 KB Output is correct
7 Correct 50 ms 195156 KB Output is correct
8 Correct 177 ms 236524 KB Output is correct
9 Correct 185 ms 236604 KB Output is correct
10 Correct 50 ms 195016 KB Output is correct
11 Correct 214 ms 235268 KB Output is correct
12 Correct 214 ms 235516 KB Output is correct
13 Correct 154 ms 236488 KB Output is correct
14 Correct 51 ms 195016 KB Output is correct
15 Correct 150 ms 224772 KB Output is correct
16 Correct 221 ms 224160 KB Output is correct
17 Correct 206 ms 224512 KB Output is correct
18 Correct 230 ms 224772 KB Output is correct
19 Correct 189 ms 229380 KB Output is correct
20 Correct 178 ms 228496 KB Output is correct
21 Correct 190 ms 229120 KB Output is correct
22 Correct 225 ms 229784 KB Output is correct
23 Correct 213 ms 225792 KB Output is correct
24 Correct 207 ms 225796 KB Output is correct
25 Correct 222 ms 231172 KB Output is correct
26 Correct 197 ms 225028 KB Output is correct
27 Correct 175 ms 225384 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 195012 KB Output is correct
2 Correct 57 ms 195804 KB Output is correct
3 Correct 57 ms 195852 KB Output is correct
4 Correct 60 ms 195788 KB Output is correct
5 Correct 60 ms 196060 KB Output is correct
6 Correct 55 ms 196100 KB Output is correct
7 Correct 50 ms 195156 KB Output is correct
8 Correct 177 ms 236524 KB Output is correct
9 Correct 185 ms 236604 KB Output is correct
10 Correct 50 ms 195016 KB Output is correct
11 Correct 214 ms 235268 KB Output is correct
12 Correct 214 ms 235516 KB Output is correct
13 Correct 154 ms 236488 KB Output is correct
14 Correct 51 ms 195016 KB Output is correct
15 Correct 150 ms 224772 KB Output is correct
16 Correct 221 ms 224160 KB Output is correct
17 Correct 206 ms 224512 KB Output is correct
18 Correct 230 ms 224772 KB Output is correct
19 Correct 189 ms 229380 KB Output is correct
20 Correct 178 ms 228496 KB Output is correct
21 Correct 190 ms 229120 KB Output is correct
22 Correct 225 ms 229784 KB Output is correct
23 Correct 213 ms 225792 KB Output is correct
24 Correct 207 ms 225796 KB Output is correct
25 Correct 222 ms 231172 KB Output is correct
26 Correct 197 ms 225028 KB Output is correct
27 Correct 175 ms 225384 KB Output is correct
28 Correct 57 ms 195188 KB Output is correct
29 Correct 371 ms 197600 KB Output is correct
30 Correct 209 ms 197920 KB Output is correct
31 Correct 281 ms 197796 KB Output is correct
32 Correct 200 ms 197896 KB Output is correct
33 Correct 234 ms 198404 KB Output is correct
34 Correct 56 ms 195012 KB Output is correct
35 Correct 1404 ms 233220 KB Output is correct
36 Correct 1678 ms 233384 KB Output is correct
37 Correct 1760 ms 233364 KB Output is correct
38 Correct 54 ms 195012 KB Output is correct
39 Execution timed out 3558 ms 231552 KB Time limit exceeded
40 Halted 0 ms 0 KB -