Submission #544654

#TimeUsernameProblemLanguageResultExecution timeMemory
544654pokmui9909트리 (KOI16_tree)C++17
100 / 100
212 ms25548 KiB
#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]);
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...