Submission #544688

#	Time	Username	Problem	Language	Result	Execution time	Memory
544688		pokmui9909	트리 (KOI16_treeM)	C++17	100 / 100	135 ms	21920 KiB

tree

#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
ll n, Q;
ll p[200005];
vector<ll> ans;
 
struct st
{
	ll t, x, y;
}qry[400005];
 
ll uf[200005];
 
ll Find(ll n)
{
	if (uf[n] == -1) return n;
	return uf[n] = Find(uf[n]);
}
 
void Union(ll x, ll y)
{
	x = Find(x), y = Find(y);
	uf[y] = x;
}
 
int main()
{
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
 
	cin >> n >> Q;
	fill(uf, uf + 200005, -1);
	for (ll i = 2; i <= n; i++) cin >> p[i];
	for (ll i = 1; i < n + Q; i++)
	{
		ll op; cin >> op;
		if (op == 0)
		{
			ll x; cin >> x;
			qry[i] = { 0, x, 0 };
		}
		else
		{
			ll x, y; cin >> x >> y;
			qry[i] = { 1, x, y };
		}
	}
	for (ll i = n + Q - 1; i >= 1; i--)
	{
		if (qry[i].t == 0) Union(qry[i].x, p[qry[i].x]);
		else ans.push_back(Find(qry[i].x) == Find(qry[i].y));
	}
	reverse(ans.begin(), ans.end());
	for (auto i : ans) cout << (i ? "YES\n" : "NO\n");
}

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