Submission #1224599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224599		SpyrosAliv	Inside information (BOI21_servers)	C++20	12 / 100	3592 ms	5344 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);

vector<int> find_seq(int u, int targ) {
    vector<int> seq;
    int lst = idx[u];
    int curr = u;
    while (true) {
        if (curr == targ) return seq;
        if (par[curr] == 0) {
            return {-1};
        }
        seq.push_back(idx[curr]);
        lst = idx[curr];
        curr = par[curr];
    }
    return seq;
}

int get_lca(int u, int v) {
    while (u != v) {
        if (u < v) swap(u, v);
        if (par[u] == 0) return -1;
        u = par[u];
    }
    return u;
}

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 lca = get_lca(u, v);
            if (lca == -1) {
                cout << "no\n";
                continue;
            }
            vector<int> seqa = find_seq(u, lca);
            vector<int> seqb = find_seq(v, lca);
            bool f = true;
            for (int i = 1; i < (int)seqb.size(); i++) {
                if (seqb[i] < seqb[i-1]) {
                    f = false;
                    break;
                }
            }
            for (int i = 1; i < (int)seqa.size(); i++) {
                if (seqa[i] > seqa[i-1]) {
                    f = false;
                    break;
                }
            }
            if (lca == u || lca == v) {
                if (f) cout << "yes\n";
                else cout << "no\n";
                continue;
            }
            if (seqb.back() > seqa.back()) f = false;
            if (f) 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;
        }
        else assert(false);
    }
}

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 0 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 10 / 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