oj.uz

Submission #107498

# Submission time Handle Problem Language Result Execution time Memory
107498 2019-04-24T22:23:54 Z aer0park None (KOI16_tree) C++14
9 / 100
 259 ms 27264 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)
{
	upd(a,qy);
	upd(a+sz,-qy);
	qy++;
}

ll dfs(ll a,ll p)
{
	ll ret=1;
	ind[a]=cnt++,par[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])&&par[f]!=0)
					updrange(f,chd[f]);
			}
			else
			{
				cout<<"NO"<<"\n";
				ll f=ind[c];
				if(val(f)==val(par[f])&&par[f]!=0)
					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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 8 ms 5248 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 6 ms 5248 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct

Subtask #2
0 / 13.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 45.0

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