답안 #107538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107538	2019-04-25T01:51:29 Z	aer0park	트리 (KOI16_tree)	C++14	41 / 100	319 ms	27792 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=200000-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	8 ms	5248 KB	Output is correct
3	Correct	8 ms	5248 KB	Output is correct
4	Correct	7 ms	5248 KB	Output is correct
5	Correct	6 ms	5120 KB	Output is correct
6	Correct	6 ms	5120 KB	Output is correct
7	Correct	7 ms	5248 KB	Output is correct
8	Correct	6 ms	5248 KB	Output is correct
9	Correct	8 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	8 ms	5248 KB	Output is correct
3	Correct	8 ms	5248 KB	Output is correct
4	Correct	7 ms	5248 KB	Output is correct
5	Correct	6 ms	5120 KB	Output is correct
6	Correct	6 ms	5120 KB	Output is correct
7	Correct	7 ms	5248 KB	Output is correct
8	Correct	6 ms	5248 KB	Output is correct
9	Correct	8 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	5120 KB	Output is correct
13	Correct	7 ms	5120 KB	Output is correct
14	Correct	9 ms	5148 KB	Output is correct
15	Correct	7 ms	5120 KB	Output is correct
16	Correct	8 ms	5120 KB	Output is correct
17	Correct	8 ms	5120 KB	Output is correct
18	Correct	6 ms	5120 KB	Output is correct
19	Correct	8 ms	5120 KB	Output is correct
20	Correct	6 ms	5120 KB	Output is correct
21	Correct	9 ms	5120 KB	Output is correct

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5248 KB	Output is correct
2	Correct	8 ms	5248 KB	Output is correct
3	Correct	8 ms	5248 KB	Output is correct
4	Correct	7 ms	5248 KB	Output is correct
5	Correct	6 ms	5120 KB	Output is correct
6	Correct	6 ms	5120 KB	Output is correct
7	Correct	7 ms	5248 KB	Output is correct
8	Correct	6 ms	5248 KB	Output is correct
9	Correct	8 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	5120 KB	Output is correct
13	Correct	7 ms	5120 KB	Output is correct
14	Correct	9 ms	5148 KB	Output is correct
15	Correct	7 ms	5120 KB	Output is correct
16	Correct	8 ms	5120 KB	Output is correct
17	Correct	8 ms	5120 KB	Output is correct
18	Correct	6 ms	5120 KB	Output is correct
19	Correct	8 ms	5120 KB	Output is correct
20	Correct	6 ms	5120 KB	Output is correct
21	Correct	9 ms	5120 KB	Output is correct
22	Correct	68 ms	5752 KB	Output is correct
23	Incorrect	91 ms	5752 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	8 ms	5248 KB	Output is correct
3	Correct	8 ms	5248 KB	Output is correct
4	Correct	7 ms	5248 KB	Output is correct
5	Correct	6 ms	5120 KB	Output is correct
6	Correct	6 ms	5120 KB	Output is correct
7	Correct	7 ms	5248 KB	Output is correct
8	Correct	6 ms	5248 KB	Output is correct
9	Correct	8 ms	5120 KB	Output is correct
10	Correct	8 ms	5248 KB	Output is correct
11	Correct	319 ms	27568 KB	Output is correct
12	Correct	281 ms	27624 KB	Output is correct
13	Correct	273 ms	27512 KB	Output is correct
14	Correct	271 ms	27600 KB	Output is correct
15	Correct	261 ms	27596 KB	Output is correct
16	Correct	264 ms	27640 KB	Output is correct
17	Correct	275 ms	27792 KB	Output is correct
18	Correct	227 ms	27612 KB	Output is correct
19	Correct	232 ms	27768 KB	Output is correct
20	Correct	252 ms	27768 KB	Output is correct
21	Correct	254 ms	27504 KB	Output is correct

Subtask #5
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5248 KB	Output is correct
2	Correct	8 ms	5248 KB	Output is correct
3	Correct	8 ms	5248 KB	Output is correct
4	Correct	7 ms	5248 KB	Output is correct
5	Correct	6 ms	5120 KB	Output is correct
6	Correct	6 ms	5120 KB	Output is correct
7	Correct	7 ms	5248 KB	Output is correct
8	Correct	6 ms	5248 KB	Output is correct
9	Correct	8 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	5120 KB	Output is correct
13	Correct	7 ms	5120 KB	Output is correct
14	Correct	9 ms	5148 KB	Output is correct
15	Correct	7 ms	5120 KB	Output is correct
16	Correct	8 ms	5120 KB	Output is correct
17	Correct	8 ms	5120 KB	Output is correct
18	Correct	6 ms	5120 KB	Output is correct
19	Correct	8 ms	5120 KB	Output is correct
20	Correct	6 ms	5120 KB	Output is correct
21	Correct	9 ms	5120 KB	Output is correct
22	Correct	68 ms	5752 KB	Output is correct
23	Incorrect	91 ms	5752 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

답안 #107538

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