Submission #1039592

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1039592	2024-07-31T05:01:21 Z	Plurm	Inside information (BOI21_servers)	C++11	5 / 100	3500 ms	43924 KB

servers

#include <bits/stdc++.h>
using namespace std;

vector<int> g[500005];
vector<int> rg[500005];
int cnt[500005];
bool search(int a, int d){
    if(a == d) return true;
    for(int v : g[a]) if(search(v, d)) return true;
    return false;
}
int count(int d){
    int ret = cnt[d];
    for(int v : rg[d]) ret += count(v);
    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]);
                g[last].push_back(ids[b]);
                rg[ids[a]].push_back(last);
                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;
        }
    }
    for(int i = 1; i <= n; i++){
        ids[i] = i;
        cnt[i]++;
    }
    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]);
                cnt[ids[a]]--;
                cnt[ids[b]]--;
                last++;
                ids[a] = ids[b] = last;
                cnt[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	26528 KB	Output is correct
2	Correct	165 ms	27336 KB	Output is correct
3	Correct	747 ms	27392 KB	Output is correct
4	Correct	176 ms	27352 KB	Output is correct
5	Correct	175 ms	27392 KB	Output is correct
6	Correct	1693 ms	27868 KB	Output is correct

Subtask #2
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	163 ms	26528 KB	Output is correct
2	Correct	165 ms	27336 KB	Output is correct
3	Correct	747 ms	27392 KB	Output is correct
4	Correct	176 ms	27352 KB	Output is correct
5	Correct	175 ms	27392 KB	Output is correct
6	Correct	1693 ms	27868 KB	Output is correct
7	Correct	191 ms	26568 KB	Output is correct
8	Correct	188 ms	27100 KB	Output is correct
9	Correct	1182 ms	27324 KB	Output is correct
10	Correct	172 ms	27060 KB	Output is correct
11	Correct	185 ms	27092 KB	Output is correct
12	Correct	1724 ms	27508 KB	Output is correct

Subtask #3
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	141 ms	26568 KB	Output is correct
2	Execution timed out	3549 ms	42632 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	141 ms	26568 KB	Output is correct
2	Execution timed out	3549 ms	42632 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	26564 KB	Output is correct
2	Correct	190 ms	41728 KB	Output is correct
3	Correct	223 ms	41728 KB	Output is correct
4	Execution timed out	3520 ms	43776 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	26564 KB	Output is correct
2	Correct	190 ms	41728 KB	Output is correct
3	Correct	223 ms	41728 KB	Output is correct
4	Execution timed out	3520 ms	43776 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	26504 KB	Output is correct
2	Execution timed out	3577 ms	42484 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	26504 KB	Output is correct
2	Execution timed out	3577 ms	42484 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	26564 KB	Output is correct
2	Correct	202 ms	41820 KB	Output is correct
3	Correct	205 ms	41732 KB	Output is correct
4	Execution timed out	3506 ms	43924 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	26564 KB	Output is correct
2	Correct	202 ms	41820 KB	Output is correct
3	Correct	205 ms	41732 KB	Output is correct
4	Execution timed out	3506 ms	43924 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	133 ms	26572 KB	Output is correct
2	Correct	151 ms	27356 KB	Output is correct
3	Correct	608 ms	27392 KB	Output is correct
4	Correct	178 ms	27844 KB	Output is correct
5	Correct	129 ms	27392 KB	Output is correct
6	Correct	1472 ms	27652 KB	Output is correct
7	Correct	144 ms	26668 KB	Output is correct
8	Execution timed out	3575 ms	42596 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	133 ms	26572 KB	Output is correct
2	Correct	151 ms	27356 KB	Output is correct
3	Correct	608 ms	27392 KB	Output is correct
4	Correct	178 ms	27844 KB	Output is correct
5	Correct	129 ms	27392 KB	Output is correct
6	Correct	1472 ms	27652 KB	Output is correct
7	Correct	144 ms	26668 KB	Output is correct
8	Execution timed out	3575 ms	42596 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Submission #1039592

Compilation message