| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 57844 |
2018-07-16T10:14:22 Z |
red1108 |
None (KOI16_tree) |
C++17 |
|
6 ms |
5112 KB |
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;
int n,q;
vector<int> tree[200010];
int seg[800010],par[200010],cnt=0,si=1,color[200010],ccnt=1,bumo[200010],cut[200010];
pair<int,int> range[200010];
int checkcnt=0;
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)
{
checkcnt++;
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()
{
freopen("input35", "r",stdin);
freopen("output.txt", "w", stdout);
int i,a,b,c,flag,tmp,sip,sia;
scanf("%d %d", &n,&q);
while(si<n)si*=2;
for(i=2; i<=n; i++)
{
scanf("%d", &a);
bumo[i]=a;
tree[a].emplace_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++,flag=0)
{
scanf("%d %d %d", &a, &b, &c);
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]) continue;
cut[a]=1;
sia=getsize(1,1,si,range[a].first+1,range[a].second)+1;
gang(range[a].first,(-1)*sia+1);
sip=getsize(1,1,si,range[par[color[a]]].first+1,range[par[color[a]]].second)+1;
if(sip<sia)
{
par[ccnt+1]=par[color[a]];
tmp=color[a];
rename(par[color[a]],++ccnt);
par[tmp]=a;
}
else
{
rename(a,++ccnt);
par[ccnt]=a;
}
}
}
Compilation message
tree.cpp: In function 'int main()':
tree.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input35", "r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
tree.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("output.txt", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
tree.cpp:43: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:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
~~~~~^~~~~~~~~~
tree.cpp:57: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 |
6 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
