답안 #107537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107537	2019-04-25T01:50:47 Z	aer0park	트리 (KOI16_tree)	C++14	41 / 100	297 ms	27768 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=23423-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	6 ms	5248 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	7 ms	5248 KB	Output is correct
5	Correct	7 ms	5248 KB	Output is correct
6	Correct	6 ms	5120 KB	Output is correct
7	Correct	7 ms	5120 KB	Output is correct
8	Correct	8 ms	5248 KB	Output is correct
9	Correct	7 ms	5120 KB	Output is correct
10	Correct	7 ms	5120 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5248 KB	Output is correct
2	Correct	6 ms	5248 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	7 ms	5248 KB	Output is correct
5	Correct	7 ms	5248 KB	Output is correct
6	Correct	6 ms	5120 KB	Output is correct
7	Correct	7 ms	5120 KB	Output is correct
8	Correct	8 ms	5248 KB	Output is correct
9	Correct	7 ms	5120 KB	Output is correct
10	Correct	7 ms	5120 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	7 ms	5120 KB	Output is correct
15	Correct	7 ms	5120 KB	Output is correct
16	Correct	8 ms	5120 KB	Output is correct
17	Correct	6 ms	5120 KB	Output is correct
18	Correct	6 ms	5120 KB	Output is correct
19	Correct	6 ms	5120 KB	Output is correct
20	Correct	8 ms	5092 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	6 ms	5248 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	7 ms	5248 KB	Output is correct
5	Correct	7 ms	5248 KB	Output is correct
6	Correct	6 ms	5120 KB	Output is correct
7	Correct	7 ms	5120 KB	Output is correct
8	Correct	8 ms	5248 KB	Output is correct
9	Correct	7 ms	5120 KB	Output is correct
10	Correct	7 ms	5120 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	7 ms	5120 KB	Output is correct
15	Correct	7 ms	5120 KB	Output is correct
16	Correct	8 ms	5120 KB	Output is correct
17	Correct	6 ms	5120 KB	Output is correct
18	Correct	6 ms	5120 KB	Output is correct
19	Correct	6 ms	5120 KB	Output is correct
20	Correct	8 ms	5092 KB	Output is correct
21	Correct	7 ms	5120 KB	Output is correct
22	Correct	64 ms	5756 KB	Output is correct
23	Incorrect	89 ms	5756 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	6 ms	5248 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	7 ms	5248 KB	Output is correct
5	Correct	7 ms	5248 KB	Output is correct
6	Correct	6 ms	5120 KB	Output is correct
7	Correct	7 ms	5120 KB	Output is correct
8	Correct	8 ms	5248 KB	Output is correct
9	Correct	7 ms	5120 KB	Output is correct
10	Correct	7 ms	5120 KB	Output is correct
11	Correct	297 ms	27544 KB	Output is correct
12	Correct	272 ms	27512 KB	Output is correct
13	Correct	276 ms	27508 KB	Output is correct
14	Correct	286 ms	27648 KB	Output is correct
15	Correct	227 ms	27548 KB	Output is correct
16	Correct	246 ms	27644 KB	Output is correct
17	Correct	273 ms	27740 KB	Output is correct
18	Correct	279 ms	27768 KB	Output is correct
19	Correct	263 ms	27768 KB	Output is correct
20	Correct	250 ms	27768 KB	Output is correct
21	Correct	230 ms	27588 KB	Output is correct

Subtask #5
0 / 45.0

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

답안 #107537

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