제출 #544654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544654		pokmui9909	트리 (KOI16_tree)	C++17	100 / 100	212 ms	25548 KiB

tree

#include <bits/stdc++.h>
using namespace std;
 
int N, Q;
int cnt = 0;
vector<int> T[200005];
int in[200005];
int out[200005];
int seg[800005];
 
void update(int node, int s, int e, int l, int r, int v)
{
    if(l <= s && e <= r) {seg[node] = max(seg[node], v); return;}
    else if(s > r || e < l) return;
    update(node * 2, s, (s + e) / 2, l, r, v);
    update(node * 2 + 1, (s + e) / 2 + 1, e, l, r, v);
}
 
int query(int node, int s, int e, int k)
{
    if(s == e) return seg[node];
    int m = (s + e) / 2;
    if(k <= m) return max(seg[node], query(node * 2, s, m, k));
    else return max(seg[node], query(node * 2 + 1, m + 1, e, k));
}
 
void dfs(int n)
{
    in[n] = ++cnt;
    for(auto i : T[n]) dfs(i);
    out[n] = cnt;
}
 
int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
 
    cin >> N >> Q;
    for(int i = 2; i <= N; i++)
    {
        int u; cin >> u;
        T[u].push_back(i);
    }
    dfs(1);
    while(Q--)
    {
        int x, y, op; cin >> x >> y >> op;
        if(op == 0) cout << (query(1, 1, N, in[x]) == query(1, 1, N, in[y]) ? "YES" : "NO") << '\n';
        else
        {
            if(query(1, 1, N, in[x]) == query(1, 1, N, in[y])) cout << "YES\n";
            else{cout << "NO\n"; swap(x, y);}
            update(1, 1, N, in[x], out[x], in[x]);
        }
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 14 / 14
• Subtask 4: 19 / 19
• Subtask 5: 45 / 45