Submission #1693884
Source Code Expand
#include<bits/stdc++.h> #define inf 1000000000 #define N 200009 using namespace std; int n,tot,cnt,tp,dfsclk,q[N],fst[N],pnt[N<<1],nxt[N<<1]; int lf[N],rg[N],id[N],anc[N],sz[N],son[N],fa[N],d[N],f[N]; long long ans; char s[N]; struct node{ int x,y; }a[N],b[N],c[N]; bool operator <(node u,node v){ return u.x<v.x; } void mdy(node &u,node v){ u.x=max(u.x,v.x); u.y=min(u.y,v.y); } void add(int x,int y){ pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot; } int find(int x,int y){ int t=x; for (; anc[x]!=anc[y]; x=fa[anc[x]]) t=anc[x]; return x==y?t:id[lf[y]+1]; } void calc(int x){ int i,y; if (b[x].x) c[cnt=1]=b[x]; else cnt=0; for (i=fst[x]; i; i=nxt[i]){ y=pnt[i]; if (y!=fa[x]) c[++cnt]=a[y]; } sort(c+1,c+cnt+1); int l=0,r=c[cnt].x-1; if (b[x].x==c[cnt].x) r=min(r,a[x].x); else{ for (i=fst[x]; i; i=nxt[i]){ y=pnt[i]; if (y!=fa[x] && c[cnt].x==a[y].x){ r=min(r,b[y].x); break; } } } cout<<x<<endl; if (s[x]=='0'){ l=inf; for (i=1; i<=cnt; i++){ //y=c[i].y; //if (!y) continue; if (i<cnt && c[i].y<inf) l=min(l,c[cnt-1].x); //else l=min(l,c[i].y+c[cnt-1].x+c[i].y); //cout<<"? "<<y<<endl; //if (lf[y]<=lf[x] && lf[x]<=rg[y]){ // y=find(x,y); // cout<<" "<<c[i].z<<endl; //} //else{ // cout<<" "<<c[i].z<<' '<<b[y].x<<endl; // l=min(l,c[i].z+b[y].x-1); //} } } cout<<" "<<l<<' '<<r<<endl; ans+=max(0,r-l+1); } void dfs(int x){ int i,y; sz[x]=1; for (i=fst[x]; i; i=nxt[i]){ y=pnt[i]; if (y!=fa[x]){ fa[y]=x; d[y]=d[x]+1; dfs(y); sz[x]+=sz[y]; if (sz[y]>sz[son[x]]) son[x]=y; mdy(a[x],a[y]); } } a[x].x++; if (s[x]=='1') a[x].y=1; } void dvd(int x,int tp){ int i,y; lf[x]=++dfsclk; id[dfsclk]=x; anc[x]=tp; if (son[x]) dvd(son[x],tp); for (i=fst[x]; i; i=nxt[i]){ y=pnt[i]; if (y!=fa[x] && y!=son[x]) dvd(y,y); } rg[x]=dfsclk; } void dfs2(int x){ int i,y; for (i=fst[x],tp=0; i; i=nxt[i]){ y=pnt[i]; if (y!=fa[x]) q[++tp]=y; } node tmp=b[x]; for (i=1; i<=tp; i++){ y=q[i]; mdy(b[y],tmp); mdy(tmp,a[y]); } for (i=tp,tmp=(node){-inf,inf}; i; i--){ y=q[i]; mdy(b[y],tmp); mdy(tmp,a[y]); } for (i=1; i<=tp; i++){ b[q[i]].x++; b[q[i]].y++; } if (s[x]=='1') for (i=1; i<=tp; i++){ b[q[i]].y=1;// b[q[i]].z=1; } for (i=fst[x]; i; i=nxt[i]){ y=pnt[i]; if (y!=fa[x]) dfs2(y); } } int main(){ scanf("%d",&n); int i,x,y; for (i=1; i<n; i++){ scanf("%d%d",&x,&y); add(x,y); add(y,x); } scanf("%s",s+1); for (i=1; i<=n; i++) a[i].y=b[i].y=inf; dfs(1); dvd(1,1); dfs2(1); for (i=1; i<=n; i++) calc(i); printf("%lld\n",ans+1); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Black Radius |
User | lych_cys |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2722 Byte |
Status | WA |
Exec Time | 816 ms |
Memory | 29056 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:115:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:118:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&x,&y); ^ ./Main.cpp:121:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s",s+1); ^
Judge Result
Set Name | Sample | Subtask | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1300 | 0 / 600 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt |
Subtask | 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt, 2_44.txt, 2_45.txt, 2_46.txt, 2_47.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | WA | 4 ms | 14592 KB |
0_01.txt | WA | 4 ms | 14592 KB |
0_02.txt | WA | 4 ms | 14592 KB |
1_00.txt | WA | 4 ms | 14592 KB |
1_01.txt | WA | 747 ms | 27776 KB |
1_02.txt | WA | 756 ms | 24320 KB |
1_03.txt | WA | 733 ms | 17920 KB |
1_04.txt | WA | 737 ms | 18304 KB |
1_05.txt | WA | 699 ms | 19328 KB |
1_06.txt | WA | 746 ms | 17536 KB |
1_07.txt | WA | 720 ms | 17536 KB |
1_08.txt | WA | 743 ms | 18304 KB |
1_09.txt | WA | 816 ms | 23680 KB |
1_10.txt | WA | 728 ms | 22016 KB |
1_11.txt | WA | 736 ms | 27648 KB |
1_12.txt | WA | 724 ms | 19840 KB |
1_13.txt | WA | 743 ms | 22272 KB |
1_14.txt | WA | 754 ms | 19584 KB |
1_15.txt | WA | 771 ms | 18688 KB |
1_16.txt | WA | 744 ms | 20480 KB |
1_17.txt | WA | 749 ms | 23424 KB |
1_18.txt | WA | 734 ms | 17664 KB |
1_19.txt | WA | 730 ms | 17536 KB |
1_20.txt | WA | 735 ms | 17920 KB |
1_21.txt | WA | 765 ms | 18432 KB |
1_22.txt | WA | 710 ms | 17920 KB |
1_23.txt | WA | 733 ms | 17792 KB |
1_24.txt | WA | 717 ms | 18304 KB |
1_25.txt | WA | 807 ms | 19584 KB |
1_26.txt | WA | 712 ms | 17792 KB |
1_27.txt | WA | 737 ms | 18176 KB |
1_28.txt | WA | 723 ms | 18816 KB |
1_29.txt | WA | 733 ms | 20352 KB |
2_00.txt | WA | 4 ms | 14592 KB |
2_01.txt | WA | 740 ms | 29056 KB |
2_02.txt | WA | 764 ms | 26752 KB |
2_03.txt | WA | 750 ms | 25728 KB |
2_04.txt | WA | 747 ms | 24320 KB |
2_05.txt | WA | 746 ms | 23808 KB |
2_06.txt | WA | 753 ms | 24064 KB |
2_07.txt | WA | 746 ms | 19584 KB |
2_08.txt | WA | 743 ms | 19584 KB |
2_09.txt | WA | 734 ms | 18176 KB |
2_10.txt | WA | 754 ms | 20096 KB |
2_11.txt | WA | 733 ms | 19968 KB |
2_12.txt | WA | 719 ms | 19328 KB |
2_13.txt | WA | 739 ms | 20992 KB |
2_14.txt | WA | 717 ms | 20992 KB |
2_15.txt | WA | 736 ms | 19840 KB |
2_16.txt | WA | 736 ms | 19200 KB |
2_17.txt | WA | 724 ms | 19200 KB |
2_18.txt | WA | 728 ms | 18944 KB |
2_19.txt | WA | 739 ms | 19328 KB |
2_20.txt | WA | 770 ms | 19200 KB |
2_21.txt | WA | 727 ms | 17664 KB |
2_22.txt | WA | 738 ms | 19968 KB |
2_23.txt | WA | 736 ms | 20352 KB |
2_24.txt | WA | 735 ms | 19200 KB |
2_25.txt | WA | 755 ms | 24576 KB |
2_26.txt | WA | 757 ms | 23296 KB |
2_27.txt | WA | 758 ms | 23424 KB |
2_28.txt | WA | 774 ms | 23040 KB |
2_29.txt | WA | 764 ms | 27008 KB |
2_30.txt | WA | 748 ms | 25728 KB |
2_31.txt | WA | 736 ms | 23168 KB |
2_32.txt | WA | 746 ms | 19456 KB |
2_33.txt | WA | 758 ms | 20736 KB |
2_34.txt | WA | 727 ms | 22272 KB |
2_35.txt | WA | 724 ms | 25344 KB |
2_36.txt | WA | 732 ms | 19584 KB |
2_37.txt | WA | 739 ms | 18560 KB |
2_38.txt | WA | 740 ms | 19712 KB |
2_39.txt | WA | 724 ms | 19328 KB |
2_40.txt | WA | 733 ms | 19712 KB |
2_41.txt | WA | 740 ms | 19072 KB |
2_42.txt | WA | 717 ms | 19968 KB |
2_43.txt | WA | 761 ms | 24192 KB |
2_44.txt | WA | 715 ms | 19968 KB |
2_45.txt | WA | 719 ms | 20352 KB |
2_46.txt | WA | 739 ms | 20608 KB |
2_47.txt | WA | 717 ms | 21376 KB |