Submission #1040524

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1040524	2024-08-01T06:51:57 Z	Plurm	Inside information (BOI21_servers)	C++11	52.5 / 100	3500 ms	81384 KB

servers

#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 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 = 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);
    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	125 ms	31432 KB	Output is correct
2	Correct	148 ms	34008 KB	Output is correct
3	Correct	131 ms	34304 KB	Output is correct
4	Correct	138 ms	34168 KB	Output is correct
5	Correct	134 ms	34560 KB	Output is correct
6	Correct	143 ms	34560 KB	Output is correct

Subtask #2
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	31432 KB	Output is correct
2	Correct	148 ms	34008 KB	Output is correct
3	Correct	131 ms	34304 KB	Output is correct
4	Correct	138 ms	34168 KB	Output is correct
5	Correct	134 ms	34560 KB	Output is correct
6	Correct	143 ms	34560 KB	Output is correct
7	Correct	244 ms	31432 KB	Output is correct
8	Correct	788 ms	36312 KB	Output is correct
9	Correct	758 ms	36356 KB	Output is correct
10	Correct	804 ms	36064 KB	Output is correct
11	Correct	987 ms	36356 KB	Output is correct
12	Correct	853 ms	36356 KB	Output is correct

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	123 ms	31428 KB	Output is correct
2	Correct	252 ms	81384 KB	Output is correct
3	Correct	224 ms	80640 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	123 ms	31428 KB	Output is correct
2	Correct	252 ms	81384 KB	Output is correct
3	Correct	224 ms	80640 KB	Output is correct
4	Correct	228 ms	31428 KB	Output is correct
5	Execution timed out	3526 ms	77564 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	31428 KB	Output is correct
2	Correct	254 ms	79652 KB	Output is correct
3	Correct	254 ms	79100 KB	Output is correct
4	Correct	215 ms	79376 KB	Output is correct

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	31428 KB	Output is correct
2	Correct	254 ms	79652 KB	Output is correct
3	Correct	254 ms	79100 KB	Output is correct
4	Correct	215 ms	79376 KB	Output is correct
5	Correct	231 ms	31380 KB	Output is correct
6	Execution timed out	3571 ms	76152 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	31592 KB	Output is correct
2	Correct	192 ms	69636 KB	Output is correct
3	Correct	227 ms	69896 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	31592 KB	Output is correct
2	Correct	192 ms	69636 KB	Output is correct
3	Correct	227 ms	69896 KB	Output is correct
4	Correct	245 ms	31592 KB	Output is correct
5	Execution timed out	3569 ms	67552 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #9
12.5 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	31544 KB	Output is correct
2	Correct	254 ms	78964 KB	Output is correct
3	Correct	256 ms	78468 KB	Output is correct
4	Correct	203 ms	80948 KB	Output is correct
5	Correct	124 ms	31440 KB	Output is correct
6	Correct	199 ms	70652 KB	Output is correct
7	Correct	227 ms	69384 KB	Output is correct
8	Correct	255 ms	70684 KB	Output is correct
9	Correct	265 ms	71260 KB	Output is correct
10	Correct	234 ms	75008 KB	Output is correct
11	Correct	239 ms	74244 KB	Output is correct

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	31544 KB	Output is correct
2	Correct	254 ms	78964 KB	Output is correct
3	Correct	256 ms	78468 KB	Output is correct
4	Correct	203 ms	80948 KB	Output is correct
5	Correct	124 ms	31440 KB	Output is correct
6	Correct	199 ms	70652 KB	Output is correct
7	Correct	227 ms	69384 KB	Output is correct
8	Correct	255 ms	70684 KB	Output is correct
9	Correct	265 ms	71260 KB	Output is correct
10	Correct	234 ms	75008 KB	Output is correct
11	Correct	239 ms	74244 KB	Output is correct
12	Correct	241 ms	31592 KB	Output is correct
13	Execution timed out	3539 ms	76296 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #11
17.5 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	123 ms	31604 KB	Output is correct
2	Correct	134 ms	34032 KB	Output is correct
3	Correct	140 ms	34364 KB	Output is correct
4	Correct	145 ms	34116 KB	Output is correct
5	Correct	141 ms	34308 KB	Output is correct
6	Correct	137 ms	34564 KB	Output is correct
7	Correct	123 ms	31500 KB	Output is correct
8	Correct	230 ms	81276 KB	Output is correct
9	Correct	222 ms	79876 KB	Output is correct
10	Correct	127 ms	31564 KB	Output is correct
11	Correct	256 ms	78460 KB	Output is correct
12	Correct	239 ms	78596 KB	Output is correct
13	Correct	207 ms	81152 KB	Output is correct
14	Correct	127 ms	31584 KB	Output is correct
15	Correct	191 ms	70604 KB	Output is correct
16	Correct	229 ms	70400 KB	Output is correct
17	Correct	240 ms	70400 KB	Output is correct
18	Correct	252 ms	69636 KB	Output is correct
19	Correct	224 ms	73984 KB	Output is correct
20	Correct	230 ms	72960 KB	Output is correct
21	Correct	252 ms	73632 KB	Output is correct
22	Correct	239 ms	73960 KB	Output is correct
23	Correct	266 ms	71428 KB	Output is correct
24	Correct	300 ms	70660 KB	Output is correct
25	Correct	255 ms	76288 KB	Output is correct
26	Correct	223 ms	71424 KB	Output is correct
27	Correct	225 ms	70892 KB	Output is correct

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	123 ms	31604 KB	Output is correct
2	Correct	134 ms	34032 KB	Output is correct
3	Correct	140 ms	34364 KB	Output is correct
4	Correct	145 ms	34116 KB	Output is correct
5	Correct	141 ms	34308 KB	Output is correct
6	Correct	137 ms	34564 KB	Output is correct
7	Correct	123 ms	31500 KB	Output is correct
8	Correct	230 ms	81276 KB	Output is correct
9	Correct	222 ms	79876 KB	Output is correct
10	Correct	127 ms	31564 KB	Output is correct
11	Correct	256 ms	78460 KB	Output is correct
12	Correct	239 ms	78596 KB	Output is correct
13	Correct	207 ms	81152 KB	Output is correct
14	Correct	127 ms	31584 KB	Output is correct
15	Correct	191 ms	70604 KB	Output is correct
16	Correct	229 ms	70400 KB	Output is correct
17	Correct	240 ms	70400 KB	Output is correct
18	Correct	252 ms	69636 KB	Output is correct
19	Correct	224 ms	73984 KB	Output is correct
20	Correct	230 ms	72960 KB	Output is correct
21	Correct	252 ms	73632 KB	Output is correct
22	Correct	239 ms	73960 KB	Output is correct
23	Correct	266 ms	71428 KB	Output is correct
24	Correct	300 ms	70660 KB	Output is correct
25	Correct	255 ms	76288 KB	Output is correct
26	Correct	223 ms	71424 KB	Output is correct
27	Correct	225 ms	70892 KB	Output is correct
28	Correct	242 ms	31432 KB	Output is correct
29	Correct	772 ms	35804 KB	Output is correct
30	Correct	756 ms	36356 KB	Output is correct
31	Correct	823 ms	36064 KB	Output is correct
32	Correct	970 ms	36340 KB	Output is correct
33	Correct	848 ms	36356 KB	Output is correct
34	Correct	232 ms	31436 KB	Output is correct
35	Execution timed out	3550 ms	77568 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-

Submission #1040524

Compilation message