oj.uz

Submission #812322

# Submission time Handle Problem Language Result Execution time Memory
812322 2023-08-07T08:22:38 Z MyCode Inside information (BOI21_servers) C++17
10 / 100
 1179 ms 377108 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    if(n <= 4000){
        set<int> st[n + 1];
        for (int i = 1; i <= n; i++)
            st[i].insert(i);
        int cnt[n + 1];
        for (int i = 1; i <= n; i++)
            cnt[i] = 1;
        for (int q = 0; q < n + k - 1; q++) {
            char t;
            cin >> t;
            if (t == 'S') {
                int a, b;
                cin >> a >> b;
                for (auto x: st[b])
                    if (st[a].find(x) == st[a].end())cnt[x]++;
                for (auto x: st[a])
                    if (st[b].find(x) == st[b].end())cnt[x]++;
                for (auto x: st[b])
                    st[a].insert(x);
                st[b] = st[a];
            } else if (t == 'Q') {
                int a, d;
                cin >> a >> d;
                if (st[a].find(d) == st[a].end())
                    cout << "no\n";
                else
                    cout << "yes\n";
            } else {
                int a;
                cin >> a;
                cout << cnt[a] << "\n";
            }
        }
        return 0;
    }
    int pos[n + 1], cur = 0;
    for (int i = 1; i <= n; i++)
        pos[i] = (int) 1e9;
    pos[1] = 0;
    for (int q = 0; q < n + k - 1; q++) {
        char t;
        cin >> t;
        if (t == 'S') {
            int a, b;
            cin >> a >> b;
            if (a != 1)swap(a, b);
            pos[b] = cur;
            cur++;
        } else if (t == 'Q') {
            int a, b;
            cin >> a >> b;
            if (a == 1) {
                if (pos[b] != (int) 1e9)
                    cout << "yes\n";
                else
                    cout << "no\n";
                continue;
            }
            if (b == 1) {
                if (pos[a] != (int) 1e9)
                    cout << "yes\n";
                else
                    cout << "no\n";
                continue;
            }
            if (pos[a] != (int)1e9 && pos[a] >= pos[b])
                cout << "yes\n";
            else
                cout << "no\n";
        } else {
            int d;
            cin >> d;
            if (d == 1) {
                cout << cur + 1 << "\n";
                continue;
            }
            if (pos[d] == (int) 1e9)cout << "1\n";
            else cout << 1 + cur - pos[d] << "\n";
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 632 KB Output is correct
2 Correct 25 ms 2140 KB Output is correct
3 Correct 149 ms 47636 KB Output is correct
4 Correct 25 ms 1836 KB Output is correct
5 Correct 24 ms 1712 KB Output is correct
6 Correct 1158 ms 376852 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 632 KB Output is correct
2 Correct 25 ms 2140 KB Output is correct
3 Correct 149 ms 47636 KB Output is correct
4 Correct 25 ms 1836 KB Output is correct
5 Correct 24 ms 1712 KB Output is correct
6 Correct 1158 ms 376852 KB Output is correct
7 Correct 17 ms 596 KB Output is correct
8 Correct 26 ms 2124 KB Output is correct
9 Correct 166 ms 59792 KB Output is correct
10 Correct 22 ms 1804 KB Output is correct
11 Correct 21 ms 1620 KB Output is correct
12 Correct 1038 ms 377108 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 692 KB Output is correct
2 Correct 38 ms 1616 KB Output is correct
3 Correct 34 ms 1568 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 692 KB Output is correct
2 Correct 38 ms 1616 KB Output is correct
3 Correct 34 ms 1568 KB Output is correct
4 Correct 17 ms 668 KB Output is correct
5 Correct 42 ms 1712 KB Output is correct
6 Correct 29 ms 1876 KB Output is correct
7 Correct 29 ms 1800 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 596 KB Output is correct
2 Incorrect 39 ms 1520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 596 KB Output is correct
2 Incorrect 39 ms 1520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 612 KB Output is correct
2 Incorrect 45 ms 3368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 612 KB Output is correct
2 Incorrect 45 ms 3368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 788 KB Output is correct
2 Incorrect 38 ms 1576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 788 KB Output is correct
2 Incorrect 38 ms 1576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 700 KB Output is correct
2 Correct 27 ms 2164 KB Output is correct
3 Correct 174 ms 47640 KB Output is correct
4 Correct 28 ms 1824 KB Output is correct
5 Correct 23 ms 1644 KB Output is correct
6 Correct 1179 ms 376844 KB Output is correct
7 Correct 20 ms 648 KB Output is correct
8 Correct 40 ms 3388 KB Output is correct
9 Correct 36 ms 3424 KB Output is correct
10 Correct 17 ms 1444 KB Output is correct
11 Incorrect 41 ms 3360 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 700 KB Output is correct
2 Correct 27 ms 2164 KB Output is correct
3 Correct 174 ms 47640 KB Output is correct
4 Correct 28 ms 1824 KB Output is correct
5 Correct 23 ms 1644 KB Output is correct
6 Correct 1179 ms 376844 KB Output is correct
7 Correct 20 ms 648 KB Output is correct
8 Correct 40 ms 3388 KB Output is correct
9 Correct 36 ms 3424 KB Output is correct
10 Correct 17 ms 1444 KB Output is correct
11 Incorrect 41 ms 3360 KB Output isn't correct
12 Halted 0 ms 0 KB -