| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26711 |
2017-07-05T09:52:10 Z |
dongwon0427 |
None (KOI16_tree) |
C++ |
|
3 ms |
36400 KB |
#include <bits/stdc++.h>
using namespace std;
int n,q;
vector<int> graph[200005];
int H[200005];
int vt[200005];
int E[200005];
vector<int> G[200005];
int depth[200005];
int dfs(int idx,int cnt) {
H[idx]=cnt;
vt[idx]=1;
//printf("%d : %d\n",idx,cnt);
for(int i=0;i<graph[idx].size();i++) {
int nxt=graph[idx][i];
if(vt[nxt]==0) {
cnt=dfs(nxt,++cnt)+1;
}
}
E[H[idx]]=cnt;
return cnt-1;
}
int ANC[200005][22];
int vtANC[200005];
void anc(int idx){
if(vtANC[idx]==1) return;
vtANC[idx]=1;
for(int i=0;i<G[idx].size();i++) {
int nxt=G[idx][i];
ANC[nxt][0]=idx;
for(int i=1;1;i++) {
if(ANC[nxt][i-1]==-1) break;
ANC[nxt][i]=ANC[ANC[nxt][i-1]][i-1];
}
if(vtANC[nxt]==0) depth[nxt]=depth[idx]+1;
anc(nxt);
}
}
int segtree[800008];
int sum(int idx,int s,int e,int k) {
if(s==e) {
return segtree[idx];
}
segtree[idx*2]=max(segtree[idx*2],segtree[idx]);
segtree[idx*2+1]=max(segtree[idx*2+1],segtree[idx]);
segtree[idx]=0;
if(s<=k && k<=(s+e)/2) {
return sum(idx*2,s,(s+e)/2,k);
} else {
return sum(idx*2+1,(s+e)/2+1,e,k);
}
}
int getA(int idx,int num) {
if(num==0) return idx;
if(num>depth[idx]) return -1;
int i=0;
while(num!=0) {
if(num%2) idx=ANC[idx][i];
num=num>>1;
i++;
}
}
void updt(int idx,int s,int e,int l,int r,int key) {
//printf("ㄴㄱㅁ\n");
if(l<=s && e<=r) {
segtree[idx]=max(segtree[idx],key);
return;
}
if(e<l || r<s) {
return;
}
updt(idx*2,s,(s+e)/2,l,r,key);
updt(idx*2+1,(s+e)/2+1,e,l,r,key);
}
int cutvt[200005];
int main() {
freopen("input.txt","r",stdin);
scanf("%d%d",&n,&q);
for(int i=2;i<=n;i++) {
int tmp;
scanf("%d",&tmp);
graph[tmp].push_back(i);
}
dfs(1,1);
//for(int i=1;i<=n;i++) printf("%d ",E[i]);
//printf("\n");
for(int i=1;i<=n;i++) {
for(int j=0;j<graph[i].size();j++) {
G[H[i]].push_back(H[graph[i][j]]);
}
}
for(int i=1;i<=n;i++) fill(ANC[i],ANC[i]+22,-1);
anc(1);
/*for(int i=1;i<=n;i++) {
printf("%d : ",i);
for(int j=0;j<G[i].size();j++) {
printf("%d ",G[i][j]);
}
printf("\n");
}*/
cutvt[1]=1;
for(int i=1;i<=q;i++) {
int t1,t2,t3;
scanf("%d%d%d",&t1,&t2,&t3);
t2=H[t2];t1=H[t1];
int a=sum(1,1,n,t1); int b=sum(1,1,n,t2);
int aA=getA(t1,depth[t1]-a);int bA=getA(t2,depth[t2]-b);
//printf("%d %d\n",depth[t1]-a,depth[t2]-b);
//printf("%d %d\n",aA,bA);
if(aA==bA) printf("YES\n");
else printf("NO\n");
if(t3==1) {
if(aA==bA) {
//앞에 제거
if(cutvt[t1]!=1) updt(1,1,n,t1,E[t1],depth[t1]);
cutvt[t1]=1;
} else {
if(cutvt[t2]!=1) updt(1,1,n,t2,E[t2],depth[t2]);
cutvt[t2]=1;
}
}
}
//printf("%d",getA(4,0));
//for(int i=1;i<=n;i++) printf("%d : %d\n",i,depth[i]);
return 0;
}
Compilation message
tree.cpp: In function 'int dfs(int, int)':
tree.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<graph[idx].size();i++) {
^
tree.cpp:17:33: warning: operation on 'cnt' may be undefined [-Wsequence-point]
cnt=dfs(nxt,++cnt)+1;
^
tree.cpp: In function 'void anc(int)':
tree.cpp:28:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[idx].size();i++) {
^
tree.cpp: In function 'int main()':
tree.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<graph[i].size();j++) {
^
tree.cpp: In function 'int getA(int, int)':
tree.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
tree.cpp: In function 'int main()':
tree.cpp:77:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input.txt","r",stdin);
^
tree.cpp:78:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&q);
^
tree.cpp:81:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&tmp);
^
tree.cpp:104:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&t1,&t2,&t3);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
36400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
36400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
36400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
36400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
36400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
