Submission #1224579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224579		SpyrosAliv	Inside information (BOI21_servers)	C++20	0 / 100	13 ms	4420 KiB

servers

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

const int MN = 120005;
const int MQ = 120005;
int n, q;
vector<vector<int>> tree(MN);
vector<int> par(MN, 0), idx(MN, 0);

int find_highest(int u, bool dec, int targ = -1) {
    int lst = idx[u];
    int curr = u;
    while (true) {
        if (curr == targ || par[curr] == 0 || (dec && idx[curr] > lst) || (!dec && idx[curr] < lst)) {
            return curr;
        }
        lst = idx[curr];
        curr = par[curr];
    }
    return curr;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int qq = 1; qq <= n + q - 1; qq++) {
        char s; cin >> s;
        if (s == 'Q') {
            int u, v; cin >> u >> v;
            int a = find_highest(u, false);
            int b = find_highest(v, true, a);
            if (a == b) {
                cout << "yes\n";
            }
            else cout << "no\n";
        }
        else if (s == 'S') {
            int a, b; cin >> a >> b;
            if (a > b) swap(a, b);
            idx[b] = qq;
            par[b] = a;
        }
        assert(s != 'C');
    }
}

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 0 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18