Submission #1040540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1040540	2024-08-01T07:03:49 Z	Plurm	Inside information (BOI21_servers)	C++11	52.5 / 100	3500 ms	232012 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 = 200;
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	163 ms	190672 KB	Output is correct
2	Correct	169 ms	191332 KB	Output is correct
3	Correct	178 ms	191488 KB	Output is correct
4	Correct	165 ms	191452 KB	Output is correct
5	Correct	162 ms	191608 KB	Output is correct
6	Correct	162 ms	191744 KB	Output is correct

Subtask #2
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	190672 KB	Output is correct
2	Correct	169 ms	191332 KB	Output is correct
3	Correct	178 ms	191488 KB	Output is correct
4	Correct	165 ms	191452 KB	Output is correct
5	Correct	162 ms	191608 KB	Output is correct
6	Correct	162 ms	191744 KB	Output is correct
7	Correct	171 ms	190644 KB	Output is correct
8	Correct	218 ms	191080 KB	Output is correct
9	Correct	208 ms	191488 KB	Output is correct
10	Correct	222 ms	191216 KB	Output is correct
11	Correct	228 ms	191492 KB	Output is correct
12	Correct	213 ms	191748 KB	Output is correct

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	157 ms	190668 KB	Output is correct
2	Correct	220 ms	226820 KB	Output is correct
3	Correct	226 ms	226764 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	157 ms	190668 KB	Output is correct
2	Correct	220 ms	226820 KB	Output is correct
3	Correct	226 ms	226764 KB	Output is correct
4	Correct	165 ms	190660 KB	Output is correct
5	Execution timed out	3558 ms	223856 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	183 ms	190740 KB	Output is correct
2	Correct	262 ms	225612 KB	Output is correct
3	Correct	262 ms	225536 KB	Output is correct
4	Correct	218 ms	226720 KB	Output is correct

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	183 ms	190740 KB	Output is correct
2	Correct	262 ms	225612 KB	Output is correct
3	Correct	262 ms	225536 KB	Output is correct
4	Correct	218 ms	226720 KB	Output is correct
5	Correct	167 ms	190756 KB	Output is correct
6	Execution timed out	3576 ms	222148 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	190744 KB	Output is correct
2	Correct	228 ms	215040 KB	Output is correct
3	Correct	274 ms	214536 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	190744 KB	Output is correct
2	Correct	228 ms	215040 KB	Output is correct
3	Correct	274 ms	214536 KB	Output is correct
4	Correct	185 ms	190664 KB	Output is correct
5	Correct	3336 ms	212224 KB	Output is correct
6	Execution timed out	3540 ms	216064 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #9
12.5 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	191428 KB	Output is correct
2	Correct	255 ms	227404 KB	Output is correct
3	Correct	250 ms	227328 KB	Output is correct
4	Correct	227 ms	228676 KB	Output is correct
5	Correct	162 ms	191432 KB	Output is correct
6	Correct	222 ms	216820 KB	Output is correct
7	Correct	252 ms	216316 KB	Output is correct
8	Correct	254 ms	216660 KB	Output is correct
9	Correct	245 ms	216764 KB	Output is correct
10	Correct	233 ms	221692 KB	Output is correct
11	Correct	275 ms	220716 KB	Output is correct

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	191428 KB	Output is correct
2	Correct	255 ms	227404 KB	Output is correct
3	Correct	250 ms	227328 KB	Output is correct
4	Correct	227 ms	228676 KB	Output is correct
5	Correct	162 ms	191432 KB	Output is correct
6	Correct	222 ms	216820 KB	Output is correct
7	Correct	252 ms	216316 KB	Output is correct
8	Correct	254 ms	216660 KB	Output is correct
9	Correct	245 ms	216764 KB	Output is correct
10	Correct	233 ms	221692 KB	Output is correct
11	Correct	275 ms	220716 KB	Output is correct
12	Correct	163 ms	191432 KB	Output is correct
13	Execution timed out	3541 ms	223932 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #11
17.5 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	155 ms	191688 KB	Output is correct
2	Correct	166 ms	192792 KB	Output is correct
3	Correct	160 ms	192780 KB	Output is correct
4	Correct	165 ms	192736 KB	Output is correct
5	Correct	186 ms	193032 KB	Output is correct
6	Correct	160 ms	193028 KB	Output is correct
7	Correct	154 ms	191692 KB	Output is correct
8	Correct	224 ms	229632 KB	Output is correct
9	Correct	221 ms	229632 KB	Output is correct
10	Correct	153 ms	191740 KB	Output is correct
11	Correct	246 ms	229120 KB	Output is correct
12	Correct	246 ms	228820 KB	Output is correct
13	Correct	211 ms	230212 KB	Output is correct
14	Correct	168 ms	191688 KB	Output is correct
15	Correct	239 ms	218372 KB	Output is correct
16	Correct	243 ms	217860 KB	Output is correct
17	Correct	258 ms	218140 KB	Output is correct
18	Correct	261 ms	218368 KB	Output is correct
19	Correct	232 ms	222980 KB	Output is correct
20	Correct	227 ms	222184 KB	Output is correct
21	Correct	235 ms	222720 KB	Output is correct
22	Correct	239 ms	223272 KB	Output is correct
23	Correct	252 ms	219372 KB	Output is correct
24	Correct	246 ms	219648 KB	Output is correct
25	Correct	238 ms	225024 KB	Output is correct
26	Correct	279 ms	219128 KB	Output is correct
27	Correct	283 ms	224768 KB	Output is correct

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	155 ms	191688 KB	Output is correct
2	Correct	166 ms	192792 KB	Output is correct
3	Correct	160 ms	192780 KB	Output is correct
4	Correct	165 ms	192736 KB	Output is correct
5	Correct	186 ms	193032 KB	Output is correct
6	Correct	160 ms	193028 KB	Output is correct
7	Correct	154 ms	191692 KB	Output is correct
8	Correct	224 ms	229632 KB	Output is correct
9	Correct	221 ms	229632 KB	Output is correct
10	Correct	153 ms	191740 KB	Output is correct
11	Correct	246 ms	229120 KB	Output is correct
12	Correct	246 ms	228820 KB	Output is correct
13	Correct	211 ms	230212 KB	Output is correct
14	Correct	168 ms	191688 KB	Output is correct
15	Correct	239 ms	218372 KB	Output is correct
16	Correct	243 ms	217860 KB	Output is correct
17	Correct	258 ms	218140 KB	Output is correct
18	Correct	261 ms	218368 KB	Output is correct
19	Correct	232 ms	222980 KB	Output is correct
20	Correct	227 ms	222184 KB	Output is correct
21	Correct	235 ms	222720 KB	Output is correct
22	Correct	239 ms	223272 KB	Output is correct
23	Correct	252 ms	219372 KB	Output is correct
24	Correct	246 ms	219648 KB	Output is correct
25	Correct	238 ms	225024 KB	Output is correct
26	Correct	279 ms	219128 KB	Output is correct
27	Correct	283 ms	224768 KB	Output is correct
28	Correct	152 ms	195784 KB	Output is correct
29	Correct	204 ms	198620 KB	Output is correct
30	Correct	193 ms	198916 KB	Output is correct
31	Correct	209 ms	198812 KB	Output is correct
32	Correct	214 ms	198912 KB	Output is correct
33	Correct	201 ms	199176 KB	Output is correct
34	Correct	157 ms	196000 KB	Output is correct
35	Execution timed out	3555 ms	232012 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-

Submission #1040540

Compilation message