Submission #107545

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
107545	2019-04-25T01:56:24 Z	aer0park	None (KOI16_tree)	C++14	41 / 100	266 ms	27896 KB

tree

#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+=n-a;
}
 
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
9.0 / 9.0

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

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	5120 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	8 ms	5248 KB	Output is correct
5	Correct	9 ms	5248 KB	Output is correct
6	Correct	7 ms	5248 KB	Output is correct
7	Correct	7 ms	5248 KB	Output is correct
8	Correct	7 ms	5248 KB	Output is correct
9	Correct	7 ms	5248 KB	Output is correct
10	Correct	7 ms	5168 KB	Output is correct
11	Correct	8 ms	5120 KB	Output is correct
12	Correct	6 ms	5120 KB	Output is correct
13	Correct	7 ms	5120 KB	Output is correct
14	Correct	7 ms	5120 KB	Output is correct
15	Correct	7 ms	5120 KB	Output is correct
16	Correct	9 ms	5120 KB	Output is correct
17	Correct	7 ms	5120 KB	Output is correct
18	Correct	7 ms	5120 KB	Output is correct
19	Correct	7 ms	5120 KB	Output is correct
20	Correct	7 ms	5120 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct

Subtask #3
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	5120 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	8 ms	5248 KB	Output is correct
5	Correct	9 ms	5248 KB	Output is correct
6	Correct	7 ms	5248 KB	Output is correct
7	Correct	7 ms	5248 KB	Output is correct
8	Correct	7 ms	5248 KB	Output is correct
9	Correct	7 ms	5248 KB	Output is correct
10	Correct	7 ms	5168 KB	Output is correct
11	Correct	8 ms	5120 KB	Output is correct
12	Correct	6 ms	5120 KB	Output is correct
13	Correct	7 ms	5120 KB	Output is correct
14	Correct	7 ms	5120 KB	Output is correct
15	Correct	7 ms	5120 KB	Output is correct
16	Correct	9 ms	5120 KB	Output is correct
17	Correct	7 ms	5120 KB	Output is correct
18	Correct	7 ms	5120 KB	Output is correct
19	Correct	7 ms	5120 KB	Output is correct
20	Correct	7 ms	5120 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct
22	Correct	89 ms	5880 KB	Output is correct
23	Correct	150 ms	5880 KB	Output is correct
24	Correct	71 ms	5952 KB	Output is correct
25	Correct	80 ms	5880 KB	Output is correct
26	Incorrect	80 ms	5832 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	5120 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	8 ms	5248 KB	Output is correct
5	Correct	9 ms	5248 KB	Output is correct
6	Correct	7 ms	5248 KB	Output is correct
7	Correct	7 ms	5248 KB	Output is correct
8	Correct	7 ms	5248 KB	Output is correct
9	Correct	7 ms	5248 KB	Output is correct
10	Correct	7 ms	5168 KB	Output is correct
11	Correct	246 ms	27532 KB	Output is correct
12	Correct	253 ms	27512 KB	Output is correct
13	Correct	235 ms	27588 KB	Output is correct
14	Correct	261 ms	27640 KB	Output is correct
15	Correct	266 ms	27512 KB	Output is correct
16	Correct	230 ms	27768 KB	Output is correct
17	Correct	249 ms	27884 KB	Output is correct
18	Correct	258 ms	27668 KB	Output is correct
19	Correct	250 ms	27896 KB	Output is correct
20	Correct	246 ms	27896 KB	Output is correct
21	Correct	233 ms	27680 KB	Output is correct

Subtask #5
0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	5120 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	8 ms	5248 KB	Output is correct
5	Correct	9 ms	5248 KB	Output is correct
6	Correct	7 ms	5248 KB	Output is correct
7	Correct	7 ms	5248 KB	Output is correct
8	Correct	7 ms	5248 KB	Output is correct
9	Correct	7 ms	5248 KB	Output is correct
10	Correct	7 ms	5168 KB	Output is correct
11	Correct	8 ms	5120 KB	Output is correct
12	Correct	6 ms	5120 KB	Output is correct
13	Correct	7 ms	5120 KB	Output is correct
14	Correct	7 ms	5120 KB	Output is correct
15	Correct	7 ms	5120 KB	Output is correct
16	Correct	9 ms	5120 KB	Output is correct
17	Correct	7 ms	5120 KB	Output is correct
18	Correct	7 ms	5120 KB	Output is correct
19	Correct	7 ms	5120 KB	Output is correct
20	Correct	7 ms	5120 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct
22	Correct	89 ms	5880 KB	Output is correct
23	Correct	150 ms	5880 KB	Output is correct
24	Correct	71 ms	5952 KB	Output is correct
25	Correct	80 ms	5880 KB	Output is correct
26	Incorrect	80 ms	5832 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Submission #107545

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 13.0 / 13.0

Subtask #3 0 / 14.0

Subtask #4 19.0 / 19.0

Subtask #5 0 / 45.0

Subtask #1
9.0 / 9.0

Subtask #2
13.0 / 13.0

Subtask #3
0 / 14.0

Subtask #4
19.0 / 19.0

Subtask #5
0 / 45.0