| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 57805 |
2018-07-16T08:36:04 Z |
red1108 |
None (KOI16_tree) |
C++17 |
|
10 ms |
5112 KB |
#include <stdio.h>
#include <vector>
using namespace std;
int n,q;
vector<int> tree[200010];
int seg[800010],par[200010],cnt=0,si=1,color[200010],ccnt=1;
pair<int,int> range[200010];
bool cut[200010];
void dfs(int x)
{
range[x].first=++cnt;
for(auto i:tree[x]) dfs(i);
range[x].second=cnt;
}
void rename(int x,int newc)
{
color[x]=newc;
for(auto i:tree[x])
{
if(!cut[i]) rename(i,newc);
}
}
void gang(int x, int k)
{
x=x+si-1;
int delta=k-seg[x];
while(x)
{
seg[x]+=delta;
x/=2;
}
}
int getsize(int x, int l, int r, int s, int e)
{
if(l>r||e<l||r<s) return 0;
if(s<=l&&r<=e) return seg[x];
return getsize(x*2,l,(l+r)/2,s,e)+getsize(x*2+1,(l+r)/2+1,r,s,e);
}
int main()
{
int i,a,b,c,flag;
scanf("%d %d", &n, &q);
while(si<n) si*=2;
for(i=2;i<=n;i++)
{
scanf("%d", &a);
tree[a].push_back(i);
}
for(i=1;i<=n;i++) color[i]=1;
par[1]=1;
dfs(1);
for(i=1;i<=n;i++){gang(i,1);}
for(i=1;i<=q;i++)
{
scanf("%d %d %d", &a, &b, &c);
flag=0;
if(color[a]==color[b]) {printf("YES\n");flag=1;}
else printf("NO\n");
if(c==0) continue;
if(!flag) a=b;
if(cut[a]==1) continue;
cut[a]=1;
gang(range[a].first,(-1)*getsize(1,1,si,range[a].first+1,range[a].second));
int sip, sia;
sip=getsize(1,1,si,range[par[color[a]]].first+1,range[par[color[a]]].second)+1;
sia=getsize(1,1,si,range[a].first+1,range[a].second)+1;
if(sip<=sia) {par[ccnt]=par[color[a]];rename(par[color[a]],++ccnt);}
else {rename(a,++ccnt);par[ccnt]=a;}
}
}
Compilation message
tree.cpp: In function 'int main()':
tree.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~
tree.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
~~~~~^~~~~~~~~~
tree.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
