oj.uz

답안 #1039592

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039592 2024-07-31T05:01:21 Z Plurm Inside information (BOI21_servers) C++11
5 / 100
 3500 ms 43924 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -