oj.uz

Submission #107528

# Submission time Handle Problem Language Result Execution time Memory
107528 2019-04-25T01:27:54 Z aer0park None (KOI16_tree) C++14
0 / 100
 10 ms 5248 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
ll n,q,cnt=1,qy=1;
ll ind[200004],pw[200004],chd[200004],par[200004];
vector<ll> g[200004];  //원래 번호 
 
ll val(ll a)
{
	ll ret=0;
	while(a)
	{
		ret+=pw[a];
		a-=(a&-a);	
	}	
	return ret;
}
 
void upd(ll a,ll x)
{
	while(a<=n)
	{
		pw[a]+=x;
		a+=(a&-a);
	}	
}
 
void updrange(ll a,ll sz)
{
	ll nw=a-val(a);
	upd(a,nw);
	upd(a+sz,-nw);
}
 
ll dfs(ll a,ll p)
{
	ll ret=1;
	ind[a]=cnt++,par[ind[a]]=ind[p];
	for(int i=0;i<g[a].size();i++)
		ret+=dfs(g[a][i],a);
	chd[ind[a]]=ret;
	return ret;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
	cin>>n>>q;
	for(int i=2;i<=n;i++)
	{
		ll a;cin>>a;
		g[a].push_back(i);
	}    
	dfs(1,0);
	for(int i=0;i<q;i++)
	{
		ll b,c,d;cin>>b>>c>>d;
		if(d==0)
		{
			if(val(ind[b])==val(ind[c]))
				cout<<"YES"<<"\n";
			else
				cout<<"NO"<<"\n";
		}
		else
		{
			if(val(ind[b])==val(ind[c]))
			{
				cout<<"YES"<<"\n";
				ll f=ind[b];
				if(val(f)==val(par[f]))
					updrange(f,chd[f]);
			}
			else
			{
				cout<<"NO"<<"\n";
				ll f=ind[c];
				if(val(f)==val(par[f]))
					updrange(f,chd[f]);	
			}
		}
	}
    return 0;
}

Compilation message

tree.cpp: In function 'll dfs(ll, ll)':
tree.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[a].size();i++)
              ~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 9 ms 5248 KB Output is correct
4 Correct 10 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Incorrect 7 ms 5248 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 9 ms 5248 KB Output is correct
4 Correct 10 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Incorrect 7 ms 5248 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 9 ms 5248 KB Output is correct
4 Correct 10 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Incorrect 7 ms 5248 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 9 ms 5248 KB Output is correct
4 Correct 10 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Incorrect 7 ms 5248 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 9 ms 5248 KB Output is correct
4 Correct 10 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Incorrect 7 ms 5248 KB Output isn't correct
7 Halted 0 ms 0 KB -