oj.uz

Submission #1040519

# Submission time Handle Problem Language Result Execution time Memory
1040519 2024-08-01T06:50:04 Z Plurm Inside information (BOI21_servers) C++11
52.5 / 100
 3500 ms 83076 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> g[500005];
vector<int> rg[500005];
int par[500005][20];
int dep[500005];
int ddep[500005];
int t;
void dfs(int u, int p = 0, int d = 0){
    ddep[u] = d;
    par[u][0] = p;
    dep[u] = dep[p]+1;
    for(int i = 1; i < 20; i++) par[u][i] = par[par[u][i-1]][i-1];
    for(int v : g[u]){
        if(v == p) continue;
        dfs(v, u, d+1);
    }
    for(int v : rg[u]){
        if(v == p) continue;
        dfs(v, u, d-1);
    }
}
int FT[500005];
void add(int idx, int amt){
    while(idx < 500005){
        FT[idx] += amt;
        idx += idx & -idx;
    }
}
int sum(int idx){
    int ret = 0;
    while(idx > 0){
        ret += FT[idx];
        idx -= idx & -idx;
    }
    return ret;
}
int lca(int u, int v){
    if(dep[u] > dep[v]) swap(u, v);
    for(int i = 19; i >= 0; i--){
        if(dep[u] <= dep[par[v][i]]) v = par[v][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--){
        if(par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}
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;
}
vector<pair<int,int>> buffer;
const int THRESH = 100;
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){
        memset(evp, 0, sizeof(evp));
        for(auto p : buffer) evp[p.first] += p.second;
        update(1);
        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);
    for(int i = 1; i <= n; i++){
        ids[i] = i;
        buffer.push_back({i, 1});
    }
    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.push_back({ids[a], -1});
                buffer.push_back({ids[b], -1});
                last++;
                ids[a] = ids[b] = last;
                buffer.push_back({last, 2});
                break;
            case 1:
                a = get<1>(cmds[i]);
                d = get<2>(cmds[i]);
                if(search(ids[a], d)) cout << "yes" << endl;
                else cout << "no" << endl;
                break;
            case 2:
                d = get<1>(cmds[i]);
                cout << count(d) << endl;
                break;
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 126 ms 33484 KB Output is correct
2 Correct 154 ms 34008 KB Output is correct
3 Correct 141 ms 34264 KB Output is correct
4 Correct 136 ms 34052 KB Output is correct
5 Correct 132 ms 34304 KB Output is correct
6 Correct 129 ms 34304 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 126 ms 33484 KB Output is correct
2 Correct 154 ms 34008 KB Output is correct
3 Correct 141 ms 34264 KB Output is correct
4 Correct 136 ms 34052 KB Output is correct
5 Correct 132 ms 34304 KB Output is correct
6 Correct 129 ms 34304 KB Output is correct
7 Correct 176 ms 35396 KB Output is correct
8 Correct 500 ms 36064 KB Output is correct
9 Correct 477 ms 37376 KB Output is correct
10 Correct 502 ms 37296 KB Output is correct
11 Correct 666 ms 37380 KB Output is correct
12 Correct 461 ms 37636 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 121 ms 33520 KB Output is correct
2 Correct 226 ms 82436 KB Output is correct
3 Correct 276 ms 82944 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 121 ms 33520 KB Output is correct
2 Correct 226 ms 82436 KB Output is correct
3 Correct 276 ms 82944 KB Output is correct
4 Correct 173 ms 29388 KB Output is correct
5 Execution timed out 3603 ms 73476 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 33480 KB Output is correct
2 Correct 247 ms 80132 KB Output is correct
3 Correct 251 ms 82176 KB Output is correct
4 Correct 206 ms 83024 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 33480 KB Output is correct
2 Correct 247 ms 80132 KB Output is correct
3 Correct 251 ms 82176 KB Output is correct
4 Correct 206 ms 83024 KB Output is correct
5 Correct 167 ms 35264 KB Output is correct
6 Execution timed out 3558 ms 78180 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 33484 KB Output is correct
2 Correct 208 ms 72304 KB Output is correct
3 Correct 225 ms 72328 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 33484 KB Output is correct
2 Correct 208 ms 72304 KB Output is correct
3 Correct 225 ms 72328 KB Output is correct
4 Correct 178 ms 35268 KB Output is correct
5 Execution timed out 3536 ms 69380 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 33492 KB Output is correct
2 Correct 263 ms 81308 KB Output is correct
3 Correct 267 ms 80900 KB Output is correct
4 Correct 225 ms 81916 KB Output is correct
5 Correct 123 ms 33476 KB Output is correct
6 Correct 250 ms 72656 KB Output is correct
7 Correct 257 ms 72448 KB Output is correct
8 Correct 284 ms 71164 KB Output is correct
9 Correct 255 ms 72324 KB Output is correct
10 Correct 225 ms 76252 KB Output is correct
11 Correct 267 ms 76236 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 33492 KB Output is correct
2 Correct 263 ms 81308 KB Output is correct
3 Correct 267 ms 80900 KB Output is correct
4 Correct 225 ms 81916 KB Output is correct
5 Correct 123 ms 33476 KB Output is correct
6 Correct 250 ms 72656 KB Output is correct
7 Correct 257 ms 72448 KB Output is correct
8 Correct 284 ms 71164 KB Output is correct
9 Correct 255 ms 72324 KB Output is correct
10 Correct 225 ms 76252 KB Output is correct
11 Correct 267 ms 76236 KB Output is correct
12 Correct 171 ms 35268 KB Output is correct
13 Execution timed out 3552 ms 78064 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 33480 KB Output is correct
2 Correct 151 ms 33892 KB Output is correct
3 Correct 154 ms 34236 KB Output is correct
4 Correct 148 ms 34036 KB Output is correct
5 Correct 132 ms 34312 KB Output is correct
6 Correct 176 ms 34308 KB Output is correct
7 Correct 135 ms 33480 KB Output is correct
8 Correct 256 ms 82180 KB Output is correct
9 Correct 259 ms 83076 KB Output is correct
10 Correct 128 ms 33492 KB Output is correct
11 Correct 263 ms 81908 KB Output is correct
12 Correct 308 ms 81788 KB Output is correct
13 Correct 246 ms 81280 KB Output is correct
14 Correct 123 ms 33500 KB Output is correct
15 Correct 212 ms 72192 KB Output is correct
16 Correct 266 ms 72764 KB Output is correct
17 Correct 281 ms 72960 KB Output is correct
18 Correct 257 ms 72144 KB Output is correct
19 Correct 235 ms 77228 KB Output is correct
20 Correct 254 ms 75268 KB Output is correct
21 Correct 244 ms 75644 KB Output is correct
22 Correct 266 ms 76748 KB Output is correct
23 Correct 280 ms 73920 KB Output is correct
24 Correct 295 ms 72684 KB Output is correct
25 Correct 290 ms 77532 KB Output is correct
26 Correct 225 ms 72192 KB Output is correct
27 Correct 297 ms 72212 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 33480 KB Output is correct
2 Correct 151 ms 33892 KB Output is correct
3 Correct 154 ms 34236 KB Output is correct
4 Correct 148 ms 34036 KB Output is correct
5 Correct 132 ms 34312 KB Output is correct
6 Correct 176 ms 34308 KB Output is correct
7 Correct 135 ms 33480 KB Output is correct
8 Correct 256 ms 82180 KB Output is correct
9 Correct 259 ms 83076 KB Output is correct
10 Correct 128 ms 33492 KB Output is correct
11 Correct 263 ms 81908 KB Output is correct
12 Correct 308 ms 81788 KB Output is correct
13 Correct 246 ms 81280 KB Output is correct
14 Correct 123 ms 33500 KB Output is correct
15 Correct 212 ms 72192 KB Output is correct
16 Correct 266 ms 72764 KB Output is correct
17 Correct 281 ms 72960 KB Output is correct
18 Correct 257 ms 72144 KB Output is correct
19 Correct 235 ms 77228 KB Output is correct
20 Correct 254 ms 75268 KB Output is correct
21 Correct 244 ms 75644 KB Output is correct
22 Correct 266 ms 76748 KB Output is correct
23 Correct 280 ms 73920 KB Output is correct
24 Correct 295 ms 72684 KB Output is correct
25 Correct 290 ms 77532 KB Output is correct
26 Correct 225 ms 72192 KB Output is correct
27 Correct 297 ms 72212 KB Output is correct
28 Correct 207 ms 35300 KB Output is correct
29 Correct 511 ms 36064 KB Output is correct
30 Correct 475 ms 37388 KB Output is correct
31 Correct 515 ms 37272 KB Output is correct
32 Correct 737 ms 37496 KB Output is correct
33 Correct 497 ms 37616 KB Output is correct
34 Correct 173 ms 36408 KB Output is correct
35 Execution timed out 3529 ms 81920 KB Time limit exceeded
36 Halted 0 ms 0 KB -