답안 #107540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107540	2019-04-25T01:53:33 Z	aer0park	트리 (KOI16_tree)	C++14	41 / 100	314 ms	27916 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=200001-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

#	결과	실행 시간	메모리	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	7 ms	5248 KB	Output is correct
5	Correct	7 ms	5120 KB	Output is correct
6	Correct	8 ms	5188 KB	Output is correct
7	Correct	7 ms	5120 KB	Output is correct
8	Correct	7 ms	5248 KB	Output is correct
9	Correct	7 ms	5120 KB	Output is correct
10	Correct	8 ms	5248 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	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	7 ms	5248 KB	Output is correct
5	Correct	7 ms	5120 KB	Output is correct
6	Correct	8 ms	5188 KB	Output is correct
7	Correct	7 ms	5120 KB	Output is correct
8	Correct	7 ms	5248 KB	Output is correct
9	Correct	7 ms	5120 KB	Output is correct
10	Correct	8 ms	5248 KB	Output is correct
11	Correct	7 ms	5120 KB	Output is correct
12	Correct	7 ms	5092 KB	Output is correct
13	Correct	7 ms	5120 KB	Output is correct
14	Correct	7 ms	5120 KB	Output is correct
15	Correct	8 ms	5148 KB	Output is correct
16	Correct	7 ms	5120 KB	Output is correct
17	Correct	8 ms	5120 KB	Output is correct
18	Correct	8 ms	5120 KB	Output is correct
19	Correct	9 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

#	결과	실행 시간	메모리	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	7 ms	5248 KB	Output is correct
5	Correct	7 ms	5120 KB	Output is correct
6	Correct	8 ms	5188 KB	Output is correct
7	Correct	7 ms	5120 KB	Output is correct
8	Correct	7 ms	5248 KB	Output is correct
9	Correct	7 ms	5120 KB	Output is correct
10	Correct	8 ms	5248 KB	Output is correct
11	Correct	7 ms	5120 KB	Output is correct
12	Correct	7 ms	5092 KB	Output is correct
13	Correct	7 ms	5120 KB	Output is correct
14	Correct	7 ms	5120 KB	Output is correct
15	Correct	8 ms	5148 KB	Output is correct
16	Correct	7 ms	5120 KB	Output is correct
17	Correct	8 ms	5120 KB	Output is correct
18	Correct	8 ms	5120 KB	Output is correct
19	Correct	9 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	75 ms	5752 KB	Output is correct
23	Incorrect	118 ms	5880 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	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	7 ms	5248 KB	Output is correct
5	Correct	7 ms	5120 KB	Output is correct
6	Correct	8 ms	5188 KB	Output is correct
7	Correct	7 ms	5120 KB	Output is correct
8	Correct	7 ms	5248 KB	Output is correct
9	Correct	7 ms	5120 KB	Output is correct
10	Correct	8 ms	5248 KB	Output is correct
11	Correct	314 ms	27552 KB	Output is correct
12	Correct	269 ms	27724 KB	Output is correct
13	Correct	268 ms	27644 KB	Output is correct
14	Correct	249 ms	27632 KB	Output is correct
15	Correct	246 ms	27652 KB	Output is correct
16	Correct	260 ms	27596 KB	Output is correct
17	Correct	252 ms	27768 KB	Output is correct
18	Correct	247 ms	27640 KB	Output is correct
19	Correct	254 ms	27916 KB	Output is correct
20	Correct	248 ms	27768 KB	Output is correct
21	Correct	250 ms	27768 KB	Output is correct

Subtask #5
0 / 45.0

#	결과	실행 시간	메모리	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	7 ms	5248 KB	Output is correct
5	Correct	7 ms	5120 KB	Output is correct
6	Correct	8 ms	5188 KB	Output is correct
7	Correct	7 ms	5120 KB	Output is correct
8	Correct	7 ms	5248 KB	Output is correct
9	Correct	7 ms	5120 KB	Output is correct
10	Correct	8 ms	5248 KB	Output is correct
11	Correct	7 ms	5120 KB	Output is correct
12	Correct	7 ms	5092 KB	Output is correct
13	Correct	7 ms	5120 KB	Output is correct
14	Correct	7 ms	5120 KB	Output is correct
15	Correct	8 ms	5148 KB	Output is correct
16	Correct	7 ms	5120 KB	Output is correct
17	Correct	8 ms	5120 KB	Output is correct
18	Correct	8 ms	5120 KB	Output is correct
19	Correct	9 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	75 ms	5752 KB	Output is correct
23	Incorrect	118 ms	5880 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

답안 #107540

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