Submission #1693710
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,z; }a[N],b[N],c[N];
bool operator <(node u,node v){ return u.x<v.x; }
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 (c[i].x<c[cnt].x) l=min(l,c[cnt-1].x);
//cout<<"? "<<y<<endl;
if (lf[y]<=lf[x] && lf[x]<=rg[y]){
y=find(x,y);
// cout<<" "<<c[i].z<<endl;
l=min(l,c[i].z+a[y].x);
}
else{
// cout<<" "<<c[i].z<<' '<<b[y].x<<endl;
l=min(l,c[i].z+b[y].x);
}
}
if (cnt>1) l=max(l,c[cnt-1].x);
}
//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;
a[x]=max(a[x],a[y]);
}
}
a[x].x++;
if (s[x]=='1'){ a[x].y=x; a[x].z=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];
b[y]=max(b[y],tmp);
tmp=max(tmp,(node){a[y].x,a[y].y,a[y].z});
}
for (i=tp,tmp.x=-inf; i; i--){
y=q[i];
b[y]=max(b[y],tmp);
tmp=max(tmp,(node){a[y].x,a[y].y,a[y].z});
}
for (i=1; i<=tp; i++){
b[q[i]].x++; b[q[i]].z++;
}
if (s[x]=='1')
for (i=1; i<=tp; i++){
b[q[i]].y=x; 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);
dfs(1); dvd(1,1);
if (s[1]=='0') b[1].z=inf; 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 |
1300 |
Code Size |
2717 Byte |
Status |
WA |
Exec Time |
126 ms |
Memory |
30976 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:114:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:117: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:120: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 |
1300 / 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 |
AC |
7 ms |
16636 KB |
0_01.txt |
AC |
6 ms |
16640 KB |
0_02.txt |
AC |
6 ms |
16640 KB |
1_00.txt |
AC |
6 ms |
16640 KB |
1_01.txt |
AC |
126 ms |
30976 KB |
1_02.txt |
AC |
112 ms |
25856 KB |
1_03.txt |
AC |
91 ms |
16768 KB |
1_04.txt |
AC |
83 ms |
17920 KB |
1_05.txt |
AC |
83 ms |
19200 KB |
1_06.txt |
AC |
98 ms |
16640 KB |
1_07.txt |
AC |
93 ms |
16640 KB |
1_08.txt |
AC |
96 ms |
17792 KB |
1_09.txt |
AC |
106 ms |
23808 KB |
1_10.txt |
AC |
103 ms |
22784 KB |
1_11.txt |
AC |
114 ms |
30848 KB |
1_12.txt |
AC |
92 ms |
20096 KB |
1_13.txt |
AC |
98 ms |
23296 KB |
1_14.txt |
AC |
84 ms |
19456 KB |
1_15.txt |
AC |
88 ms |
18176 KB |
1_16.txt |
AC |
97 ms |
20608 KB |
1_17.txt |
AC |
114 ms |
22272 KB |
1_18.txt |
AC |
96 ms |
16640 KB |
1_19.txt |
AC |
90 ms |
16640 KB |
1_20.txt |
AC |
100 ms |
16896 KB |
1_21.txt |
AC |
101 ms |
17664 KB |
1_22.txt |
AC |
81 ms |
17408 KB |
1_23.txt |
AC |
90 ms |
17152 KB |
1_24.txt |
AC |
86 ms |
17792 KB |
1_25.txt |
AC |
85 ms |
19712 KB |
1_26.txt |
AC |
86 ms |
17152 KB |
1_27.txt |
AC |
88 ms |
17792 KB |
1_28.txt |
AC |
86 ms |
18816 KB |
1_29.txt |
AC |
111 ms |
20608 KB |
2_00.txt |
AC |
6 ms |
16640 KB |
2_01.txt |
AC |
119 ms |
30336 KB |
2_02.txt |
AC |
115 ms |
28160 KB |
2_03.txt |
AC |
123 ms |
27392 KB |
2_04.txt |
AC |
105 ms |
23552 KB |
2_05.txt |
AC |
123 ms |
23808 KB |
2_06.txt |
AC |
114 ms |
24832 KB |
2_07.txt |
AC |
96 ms |
16640 KB |
2_08.txt |
WA |
96 ms |
16768 KB |
2_09.txt |
AC |
96 ms |
16640 KB |
2_10.txt |
AC |
80 ms |
17920 KB |
2_11.txt |
AC |
84 ms |
17920 KB |
2_12.txt |
AC |
86 ms |
17920 KB |
2_13.txt |
AC |
78 ms |
19200 KB |
2_14.txt |
AC |
72 ms |
19200 KB |
2_15.txt |
AC |
91 ms |
19200 KB |
2_16.txt |
WA |
93 ms |
16640 KB |
2_17.txt |
WA |
90 ms |
16640 KB |
2_18.txt |
WA |
96 ms |
16640 KB |
2_19.txt |
WA |
94 ms |
16640 KB |
2_20.txt |
WA |
86 ms |
16640 KB |
2_21.txt |
WA |
89 ms |
16640 KB |
2_22.txt |
WA |
91 ms |
17664 KB |
2_23.txt |
WA |
95 ms |
18432 KB |
2_24.txt |
WA |
89 ms |
18176 KB |
2_25.txt |
AC |
94 ms |
24320 KB |
2_26.txt |
WA |
103 ms |
22784 KB |
2_27.txt |
WA |
120 ms |
24192 KB |
2_28.txt |
WA |
104 ms |
22144 KB |
2_29.txt |
WA |
115 ms |
28672 KB |
2_30.txt |
AC |
123 ms |
26624 KB |
2_31.txt |
WA |
101 ms |
22400 KB |
2_32.txt |
WA |
88 ms |
17024 KB |
2_33.txt |
WA |
103 ms |
19712 KB |
2_34.txt |
WA |
107 ms |
21888 KB |
2_35.txt |
WA |
111 ms |
25344 KB |
2_36.txt |
WA |
95 ms |
16640 KB |
2_37.txt |
WA |
94 ms |
16640 KB |
2_38.txt |
WA |
98 ms |
18048 KB |
2_39.txt |
WA |
101 ms |
16896 KB |
2_40.txt |
WA |
86 ms |
17408 KB |
2_41.txt |
WA |
78 ms |
16896 KB |
2_42.txt |
WA |
83 ms |
17920 KB |
2_43.txt |
WA |
95 ms |
23680 KB |
2_44.txt |
WA |
82 ms |
17920 KB |
2_45.txt |
WA |
75 ms |
18944 KB |
2_46.txt |
WA |
84 ms |
19200 KB |
2_47.txt |
WA |
93 ms |
21632 KB |