Submission #1040542

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1040542	2024-08-01T07:05:59 Z	Plurm	Inside information (BOI21_servers)	C++11	52.5 / 100	3500 ms	232816 KB

servers

#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))]);
        }
    }
}
pair<int,int> rmq(int l, int r){
    int d = r-l+1;
    int lg = 31 - __builtin_clz(d);
    return min(sparse[lg][l], sparse[lg][r-(1<<lg)+1]);
}
int lca(int u, int v){
    if(st[u] > st[v]) swap(u, v);
    return rmq(st[u], st[v]).second;
}
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 = 300;
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.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	145 ms	195016 KB	Output is correct
2	Correct	159 ms	195512 KB	Output is correct
3	Correct	160 ms	195844 KB	Output is correct
4	Correct	158 ms	195808 KB	Output is correct
5	Correct	156 ms	196076 KB	Output is correct
6	Correct	157 ms	196044 KB	Output is correct

Subtask #2
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	195016 KB	Output is correct
2	Correct	159 ms	195512 KB	Output is correct
3	Correct	160 ms	195844 KB	Output is correct
4	Correct	158 ms	195808 KB	Output is correct
5	Correct	156 ms	196076 KB	Output is correct
6	Correct	157 ms	196044 KB	Output is correct
7	Correct	154 ms	195012 KB	Output is correct
8	Correct	221 ms	197524 KB	Output is correct
9	Correct	198 ms	197704 KB	Output is correct
10	Correct	221 ms	197648 KB	Output is correct
11	Correct	232 ms	197720 KB	Output is correct
12	Correct	224 ms	198028 KB	Output is correct

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	195016 KB	Output is correct
2	Correct	212 ms	231756 KB	Output is correct
3	Correct	213 ms	232408 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	195016 KB	Output is correct
2	Correct	212 ms	231756 KB	Output is correct
3	Correct	213 ms	232408 KB	Output is correct
4	Correct	152 ms	195136 KB	Output is correct
5	Execution timed out	3539 ms	229304 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	195016 KB	Output is correct
2	Correct	242 ms	230868 KB	Output is correct
3	Correct	230 ms	231124 KB	Output is correct
4	Correct	208 ms	231296 KB	Output is correct

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	195016 KB	Output is correct
2	Correct	242 ms	230868 KB	Output is correct
3	Correct	230 ms	231124 KB	Output is correct
4	Correct	208 ms	231296 KB	Output is correct
5	Correct	154 ms	195060 KB	Output is correct
6	Execution timed out	3580 ms	227980 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	195012 KB	Output is correct
2	Correct	203 ms	220448 KB	Output is correct
3	Correct	257 ms	220160 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	195012 KB	Output is correct
2	Correct	203 ms	220448 KB	Output is correct
3	Correct	257 ms	220160 KB	Output is correct
4	Correct	153 ms	195004 KB	Output is correct
5	Correct	2294 ms	217752 KB	Output is correct
6	Execution timed out	3565 ms	222980 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #9
12.5 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	152 ms	195012 KB	Output is correct
2	Correct	249 ms	231348 KB	Output is correct
3	Correct	236 ms	231164 KB	Output is correct
4	Correct	206 ms	231664 KB	Output is correct
5	Correct	152 ms	195208 KB	Output is correct
6	Correct	203 ms	220440 KB	Output is correct
7	Correct	224 ms	219932 KB	Output is correct
8	Correct	232 ms	220932 KB	Output is correct
9	Correct	232 ms	221316 KB	Output is correct
10	Correct	236 ms	224932 KB	Output is correct
11	Correct	225 ms	223492 KB	Output is correct

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	152 ms	195012 KB	Output is correct
2	Correct	249 ms	231348 KB	Output is correct
3	Correct	236 ms	231164 KB	Output is correct
4	Correct	206 ms	231664 KB	Output is correct
5	Correct	152 ms	195208 KB	Output is correct
6	Correct	203 ms	220440 KB	Output is correct
7	Correct	224 ms	219932 KB	Output is correct
8	Correct	232 ms	220932 KB	Output is correct
9	Correct	232 ms	221316 KB	Output is correct
10	Correct	236 ms	224932 KB	Output is correct
11	Correct	225 ms	223492 KB	Output is correct
12	Correct	168 ms	195012 KB	Output is correct
13	Execution timed out	3540 ms	228148 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #11
17.5 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	162 ms	194924 KB	Output is correct
2	Correct	155 ms	195632 KB	Output is correct
3	Correct	153 ms	195844 KB	Output is correct
4	Correct	154 ms	195812 KB	Output is correct
5	Correct	156 ms	196104 KB	Output is correct
6	Correct	156 ms	196116 KB	Output is correct
7	Correct	146 ms	195104 KB	Output is correct
8	Correct	215 ms	231296 KB	Output is correct
9	Correct	217 ms	232564 KB	Output is correct
10	Correct	146 ms	195048 KB	Output is correct
11	Correct	234 ms	231164 KB	Output is correct
12	Correct	237 ms	230580 KB	Output is correct
13	Correct	213 ms	232816 KB	Output is correct
14	Correct	145 ms	195016 KB	Output is correct
15	Correct	199 ms	219392 KB	Output is correct
16	Correct	225 ms	220412 KB	Output is correct
17	Correct	257 ms	220668 KB	Output is correct
18	Correct	227 ms	220164 KB	Output is correct
19	Correct	223 ms	224772 KB	Output is correct
20	Correct	225 ms	223748 KB	Output is correct
21	Correct	236 ms	225280 KB	Output is correct
22	Correct	234 ms	225076 KB	Output is correct
23	Correct	236 ms	221692 KB	Output is correct
24	Correct	232 ms	221952 KB	Output is correct
25	Correct	242 ms	226048 KB	Output is correct
26	Correct	232 ms	219840 KB	Output is correct
27	Correct	214 ms	221436 KB	Output is correct

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	162 ms	194924 KB	Output is correct
2	Correct	155 ms	195632 KB	Output is correct
3	Correct	153 ms	195844 KB	Output is correct
4	Correct	154 ms	195812 KB	Output is correct
5	Correct	156 ms	196104 KB	Output is correct
6	Correct	156 ms	196116 KB	Output is correct
7	Correct	146 ms	195104 KB	Output is correct
8	Correct	215 ms	231296 KB	Output is correct
9	Correct	217 ms	232564 KB	Output is correct
10	Correct	146 ms	195048 KB	Output is correct
11	Correct	234 ms	231164 KB	Output is correct
12	Correct	237 ms	230580 KB	Output is correct
13	Correct	213 ms	232816 KB	Output is correct
14	Correct	145 ms	195016 KB	Output is correct
15	Correct	199 ms	219392 KB	Output is correct
16	Correct	225 ms	220412 KB	Output is correct
17	Correct	257 ms	220668 KB	Output is correct
18	Correct	227 ms	220164 KB	Output is correct
19	Correct	223 ms	224772 KB	Output is correct
20	Correct	225 ms	223748 KB	Output is correct
21	Correct	236 ms	225280 KB	Output is correct
22	Correct	234 ms	225076 KB	Output is correct
23	Correct	236 ms	221692 KB	Output is correct
24	Correct	232 ms	221952 KB	Output is correct
25	Correct	242 ms	226048 KB	Output is correct
26	Correct	232 ms	219840 KB	Output is correct
27	Correct	214 ms	221436 KB	Output is correct
28	Correct	158 ms	195520 KB	Output is correct
29	Correct	222 ms	197336 KB	Output is correct
30	Correct	199 ms	197788 KB	Output is correct
31	Correct	219 ms	197504 KB	Output is correct
32	Correct	248 ms	197908 KB	Output is correct
33	Correct	243 ms	198148 KB	Output is correct
34	Correct	151 ms	195020 KB	Output is correct
35	Execution timed out	3573 ms	229576 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-

Submission #1040542

Compilation message