Submission #140675

#	Time	Username	Problem	Language	Result	Execution time	Memory
140675		khrbuddy03	트리 (KOI16_treeM)	C++14	100 / 100	185 ms	25816 KiB

tree

#include <bits/stdc++.h>

using namespace std;

const int inf = 2e5 + 9;

int par[inf];

struct query {
    int a, b, c;
    query(int _a, int _b, int _c) : a(_a), b(_b), c(_c) {}
};

struct ds {
    int par[inf];
    int find(int u) {
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }
    
    void merge(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return;
        par[u] = v;
    }
} tree;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) tree.par[i] = i;
    for (int i = 2; i <= n; i++) cin >> par[i];
    vector<query> queries;
    for (int i = 0; i < n - 1 + m; i++) {
        int x; cin >> x;
        if (x == 0) {
            int a; cin >> a;
            queries.emplace_back(0, a, 0);
        } else {
            int a, b; cin >> a >> b;
            queries.emplace_back(1, a, b);
        }
    }
    reverse(queries.begin(), queries.end());
    vector<string> ans;
    for (auto q : queries) {
        if (q.a == 0) tree.merge(q.b, par[q.b]);
        else {
            int u = tree.find(q.b), v = tree.find(q.c);
            if (u == v) ans.push_back("YES");
            else ans.push_back("NO");
        }
    }
    reverse(ans.begin(), ans.end());
    for (auto aa : ans) {
        cout << aa << '\n';
    }
}

• Subtask 1: 22 / 22
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 29 / 29