Submission #1695070
Source Code Expand
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
typedef long long LL;
const int maxn = 200005;
int ehead[maxn],ecnt;
struct edge {
int u,v,next;
}edg[maxn<<1];
void add(int u,int v) {
edg[++ecnt]=(edge){u,v,ehead[u]};
ehead[u]=ecnt;
edg[++ecnt]=(edge){v,u,ehead[v]};
ehead[v]=ecnt;
}
char s[maxn];int n,low[maxn],high[maxn];LL ans;
int fa[maxn],f[maxn],g[maxn],stk[maxn],top,pos[maxn],idx;
int pre[maxn],suf[maxn],lowf[maxn],d[maxn];
void upd(int &x,int y) {x<y?x=y:0;}
void dnd(int &x,int y) {x>y?x=y:0;}
void dfs(int u) {
low[u]=lowf[u]=1<<29;pos[++idx]=u;
if (s[u]=='1') low[u]=0;
for (int v,j=ehead[u];j;j=edg[j].next)
if ((v=edg[j].v)!=fa[u]) {
fa[v]=u;dfs(v);f[u]=max(f[u],f[v]+1);
low[u]=min(low[u],max(low[v]-1,f[v]+1));
}
}
void solve(int u) {
int mx1=0,mx2=0,cur;top=0;
g[u]>mx1?(mx2=mx1,mx1=g[u]):(g[u]>mx2?mx2=g[u]:0);
for (int v,j=ehead[u];j;j=edg[j].next)
if ((v=edg[j].v)!=fa[u]) stk[++top]=v;
pre[0]=suf[top+1]=g[u];
for (int i=1;i<=top;i++) pre[i]=max(pre[i-1],f[stk[i]]+1);
for (int i=top;i>=1;i--) suf[i]=max(suf[i+1],f[stk[i]]+1);
for (int i=1;i<=top;i++) d[i]=max(pre[i-1],suf[i+1]);
cur=lowf[u];
for (int i=1;i<=top;i++) {
int v=stk[i],res=f[v]+1,dis=d[i];
int w=max(f[v]+1,low[v]-1);
res>mx1?(mx2=mx1,mx1=res):(res>mx2?mx2=res:0);
upd(g[v],dis+1);
dnd(lowf[v],max(cur-1,dis+1));
dnd(cur,w);
}
cur=lowf[u];
for (int i=top;i>=1;i--) {
int v=stk[i],dis=d[i];
int w=max(f[v]+1,low[v]-1);
dnd(lowf[v],max(cur-1,dis+1));
dnd(cur,w);
}
low[u]=min(low[u],lowf[u]);
high[u]=min(mx1-1,mx2+1);
}
int main()
{
#ifdef Amberframe
freopen("agc008f.in","r",stdin);
freopen("agc008f.out","w",stdout);
#endif
scanf("%d",&n);
for (int u,v,i=1;i<n;i++)
scanf("%d %d",&u,&v),add(u,v);
scanf("%s",s+1);dfs(1);
for (int i=1;i<=n;i++) solve(pos[i]);
for (int i=1;i<=n;i++)
ans+=max(0,high[i]-low[i]+1);
printf("%lld",ans+1);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Black Radius |
User |
Amberframe |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
2045 Byte |
Status |
WA |
Exec Time |
84 ms |
Memory |
20352 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:72:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:74:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&u,&v),add(u,v);
^
./Main.cpp:75:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s+1);dfs(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 |
4 ms |
8448 KB |
0_01.txt |
AC |
4 ms |
8448 KB |
0_02.txt |
AC |
4 ms |
8448 KB |
1_00.txt |
AC |
4 ms |
8448 KB |
1_01.txt |
AC |
76 ms |
20352 KB |
1_02.txt |
AC |
68 ms |
17792 KB |
1_03.txt |
AC |
65 ms |
13312 KB |
1_04.txt |
AC |
59 ms |
14080 KB |
1_05.txt |
AC |
55 ms |
14464 KB |
1_06.txt |
AC |
61 ms |
13312 KB |
1_07.txt |
AC |
62 ms |
13312 KB |
1_08.txt |
AC |
63 ms |
13824 KB |
1_09.txt |
AC |
67 ms |
16768 KB |
1_10.txt |
AC |
71 ms |
16256 KB |
1_11.txt |
AC |
73 ms |
20224 KB |
1_12.txt |
AC |
64 ms |
14720 KB |
1_13.txt |
AC |
73 ms |
16512 KB |
1_14.txt |
AC |
66 ms |
14592 KB |
1_15.txt |
AC |
72 ms |
13952 KB |
1_16.txt |
AC |
67 ms |
15232 KB |
1_17.txt |
AC |
68 ms |
16000 KB |
1_18.txt |
AC |
75 ms |
13184 KB |
1_19.txt |
AC |
65 ms |
13184 KB |
1_20.txt |
AC |
63 ms |
13312 KB |
1_21.txt |
AC |
74 ms |
13696 KB |
1_22.txt |
AC |
60 ms |
13696 KB |
1_23.txt |
AC |
62 ms |
13568 KB |
1_24.txt |
AC |
64 ms |
13824 KB |
1_25.txt |
AC |
67 ms |
14976 KB |
1_26.txt |
AC |
68 ms |
13440 KB |
1_27.txt |
AC |
70 ms |
13952 KB |
1_28.txt |
AC |
61 ms |
14464 KB |
1_29.txt |
AC |
67 ms |
15360 KB |
2_00.txt |
AC |
4 ms |
8448 KB |
2_01.txt |
WA |
74 ms |
20096 KB |
2_02.txt |
AC |
69 ms |
18944 KB |
2_03.txt |
AC |
83 ms |
18688 KB |
2_04.txt |
AC |
72 ms |
16768 KB |
2_05.txt |
AC |
72 ms |
16768 KB |
2_06.txt |
AC |
71 ms |
17280 KB |
2_07.txt |
AC |
68 ms |
13312 KB |
2_08.txt |
AC |
64 ms |
13312 KB |
2_09.txt |
AC |
65 ms |
13312 KB |
2_10.txt |
AC |
68 ms |
14080 KB |
2_11.txt |
AC |
72 ms |
14080 KB |
2_12.txt |
AC |
64 ms |
14080 KB |
2_13.txt |
AC |
58 ms |
14464 KB |
2_14.txt |
AC |
64 ms |
14464 KB |
2_15.txt |
AC |
57 ms |
14464 KB |
2_16.txt |
AC |
65 ms |
13312 KB |
2_17.txt |
AC |
68 ms |
13184 KB |
2_18.txt |
WA |
65 ms |
13184 KB |
2_19.txt |
AC |
67 ms |
13312 KB |
2_20.txt |
AC |
66 ms |
13312 KB |
2_21.txt |
AC |
64 ms |
13312 KB |
2_22.txt |
AC |
71 ms |
13824 KB |
2_23.txt |
AC |
73 ms |
14080 KB |
2_24.txt |
AC |
84 ms |
13952 KB |
2_25.txt |
WA |
70 ms |
17024 KB |
2_26.txt |
AC |
71 ms |
16384 KB |
2_27.txt |
AC |
71 ms |
17024 KB |
2_28.txt |
AC |
65 ms |
16000 KB |
2_29.txt |
AC |
70 ms |
19200 KB |
2_30.txt |
AC |
72 ms |
18176 KB |
2_31.txt |
AC |
67 ms |
16128 KB |
2_32.txt |
AC |
63 ms |
13440 KB |
2_33.txt |
AC |
65 ms |
14720 KB |
2_34.txt |
AC |
64 ms |
15744 KB |
2_35.txt |
AC |
68 ms |
17408 KB |
2_36.txt |
AC |
64 ms |
13184 KB |
2_37.txt |
AC |
68 ms |
13184 KB |
2_38.txt |
AC |
63 ms |
13824 KB |
2_39.txt |
AC |
64 ms |
13312 KB |
2_40.txt |
AC |
61 ms |
13824 KB |
2_41.txt |
AC |
62 ms |
13312 KB |
2_42.txt |
AC |
57 ms |
13952 KB |
2_43.txt |
AC |
67 ms |
16768 KB |
2_44.txt |
AC |
62 ms |
13952 KB |
2_45.txt |
AC |
56 ms |
14336 KB |
2_46.txt |
AC |
56 ms |
14464 KB |
2_47.txt |
AC |
62 ms |
15744 KB |