Submission #1040541

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1040541	2024-08-01T07:05:07 Z	Plurm	Inside information (BOI21_servers)	C++11	52.5 / 100	3500 ms	235704 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 = 50;
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	161 ms	195932 KB	Output is correct
2	Correct	155 ms	196876 KB	Output is correct
3	Correct	169 ms	197120 KB	Output is correct
4	Correct	171 ms	197080 KB	Output is correct
5	Correct	154 ms	197624 KB	Output is correct
6	Correct	151 ms	197336 KB	Output is correct

Subtask #2
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	161 ms	195932 KB	Output is correct
2	Correct	155 ms	196876 KB	Output is correct
3	Correct	169 ms	197120 KB	Output is correct
4	Correct	171 ms	197080 KB	Output is correct
5	Correct	154 ms	197624 KB	Output is correct
6	Correct	151 ms	197336 KB	Output is correct
7	Correct	147 ms	196000 KB	Output is correct
8	Correct	188 ms	198616 KB	Output is correct
9	Correct	175 ms	198948 KB	Output is correct
10	Correct	191 ms	198624 KB	Output is correct
11	Correct	182 ms	198936 KB	Output is correct
12	Correct	170 ms	199228 KB	Output is correct

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	196028 KB	Output is correct
2	Correct	212 ms	235264 KB	Output is correct
3	Correct	217 ms	235264 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	196028 KB	Output is correct
2	Correct	212 ms	235264 KB	Output is correct
3	Correct	217 ms	235264 KB	Output is correct
4	Correct	146 ms	195872 KB	Output is correct
5	Execution timed out	3538 ms	231944 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	195932 KB	Output is correct
2	Correct	240 ms	234712 KB	Output is correct
3	Correct	241 ms	235132 KB	Output is correct
4	Correct	201 ms	235704 KB	Output is correct

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	195932 KB	Output is correct
2	Correct	240 ms	234712 KB	Output is correct
3	Correct	241 ms	235132 KB	Output is correct
4	Correct	201 ms	235704 KB	Output is correct
5	Correct	148 ms	195952 KB	Output is correct
6	Execution timed out	3533 ms	230876 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	195920 KB	Output is correct
2	Correct	216 ms	224728 KB	Output is correct
3	Correct	235 ms	222156 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	195920 KB	Output is correct
2	Correct	216 ms	224728 KB	Output is correct
3	Correct	235 ms	222156 KB	Output is correct
4	Correct	146 ms	195784 KB	Output is correct
5	Execution timed out	3513 ms	220416 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #9
12.5 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	195784 KB	Output is correct
2	Correct	237 ms	233216 KB	Output is correct
3	Correct	233 ms	235264 KB	Output is correct
4	Correct	211 ms	235012 KB	Output is correct
5	Correct	153 ms	195784 KB	Output is correct
6	Correct	210 ms	224104 KB	Output is correct
7	Correct	230 ms	223232 KB	Output is correct
8	Correct	223 ms	222464 KB	Output is correct
9	Correct	249 ms	224092 KB	Output is correct
10	Correct	224 ms	227544 KB	Output is correct
11	Correct	224 ms	227484 KB	Output is correct

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	195784 KB	Output is correct
2	Correct	237 ms	233216 KB	Output is correct
3	Correct	233 ms	235264 KB	Output is correct
4	Correct	211 ms	235012 KB	Output is correct
5	Correct	153 ms	195784 KB	Output is correct
6	Correct	210 ms	224104 KB	Output is correct
7	Correct	230 ms	223232 KB	Output is correct
8	Correct	223 ms	222464 KB	Output is correct
9	Correct	249 ms	224092 KB	Output is correct
10	Correct	224 ms	227544 KB	Output is correct
11	Correct	224 ms	227484 KB	Output is correct
12	Correct	152 ms	195784 KB	Output is correct
13	Execution timed out	3600 ms	229120 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #11
17.5 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	195016 KB	Output is correct
2	Correct	158 ms	195516 KB	Output is correct
3	Correct	154 ms	195840 KB	Output is correct
4	Correct	159 ms	195808 KB	Output is correct
5	Correct	149 ms	196096 KB	Output is correct
6	Correct	154 ms	196128 KB	Output is correct
7	Correct	153 ms	195012 KB	Output is correct
8	Correct	230 ms	231848 KB	Output is correct
9	Correct	206 ms	231684 KB	Output is correct
10	Correct	173 ms	195020 KB	Output is correct
11	Correct	238 ms	230656 KB	Output is correct
12	Correct	251 ms	230400 KB	Output is correct
13	Correct	203 ms	232704 KB	Output is correct
14	Correct	146 ms	195016 KB	Output is correct
15	Correct	206 ms	221440 KB	Output is correct
16	Correct	228 ms	219652 KB	Output is correct
17	Correct	239 ms	220812 KB	Output is correct
18	Correct	228 ms	221184 KB	Output is correct
19	Correct	223 ms	224716 KB	Output is correct
20	Correct	217 ms	224212 KB	Output is correct
21	Correct	217 ms	225152 KB	Output is correct
22	Correct	238 ms	224656 KB	Output is correct
23	Correct	231 ms	222412 KB	Output is correct
24	Correct	233 ms	221184 KB	Output is correct
25	Correct	226 ms	226916 KB	Output is correct
26	Correct	225 ms	221012 KB	Output is correct
27	Correct	223 ms	221440 KB	Output is correct

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	195016 KB	Output is correct
2	Correct	158 ms	195516 KB	Output is correct
3	Correct	154 ms	195840 KB	Output is correct
4	Correct	159 ms	195808 KB	Output is correct
5	Correct	149 ms	196096 KB	Output is correct
6	Correct	154 ms	196128 KB	Output is correct
7	Correct	153 ms	195012 KB	Output is correct
8	Correct	230 ms	231848 KB	Output is correct
9	Correct	206 ms	231684 KB	Output is correct
10	Correct	173 ms	195020 KB	Output is correct
11	Correct	238 ms	230656 KB	Output is correct
12	Correct	251 ms	230400 KB	Output is correct
13	Correct	203 ms	232704 KB	Output is correct
14	Correct	146 ms	195016 KB	Output is correct
15	Correct	206 ms	221440 KB	Output is correct
16	Correct	228 ms	219652 KB	Output is correct
17	Correct	239 ms	220812 KB	Output is correct
18	Correct	228 ms	221184 KB	Output is correct
19	Correct	223 ms	224716 KB	Output is correct
20	Correct	217 ms	224212 KB	Output is correct
21	Correct	217 ms	225152 KB	Output is correct
22	Correct	238 ms	224656 KB	Output is correct
23	Correct	231 ms	222412 KB	Output is correct
24	Correct	233 ms	221184 KB	Output is correct
25	Correct	226 ms	226916 KB	Output is correct
26	Correct	225 ms	221012 KB	Output is correct
27	Correct	223 ms	221440 KB	Output is correct
28	Correct	147 ms	195088 KB	Output is correct
29	Correct	187 ms	197516 KB	Output is correct
30	Correct	170 ms	197772 KB	Output is correct
31	Correct	193 ms	197600 KB	Output is correct
32	Correct	178 ms	197888 KB	Output is correct
33	Correct	171 ms	197996 KB	Output is correct
34	Correct	150 ms	195012 KB	Output is correct
35	Execution timed out	3566 ms	229396 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-

Submission #1040541

Compilation message