Submission #1695101
Source Code Expand
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
typedef long long LL;
const int maxn = 400005;
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]=lowf[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 |
1900 |
Code Size |
2050 Byte |
Status |
AC |
Exec Time |
101 ms |
Memory |
29184 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:71:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:73: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:74: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 |
600 / 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 |
6 ms |
16640 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 |
82 ms |
29184 KB |
1_02.txt |
AC |
77 ms |
26624 KB |
1_03.txt |
AC |
77 ms |
22016 KB |
1_04.txt |
AC |
66 ms |
22400 KB |
1_05.txt |
AC |
74 ms |
22784 KB |
1_06.txt |
AC |
74 ms |
22016 KB |
1_07.txt |
AC |
75 ms |
22016 KB |
1_08.txt |
AC |
77 ms |
22528 KB |
1_09.txt |
AC |
82 ms |
25600 KB |
1_10.txt |
AC |
87 ms |
25088 KB |
1_11.txt |
AC |
84 ms |
29056 KB |
1_12.txt |
AC |
82 ms |
23680 KB |
1_13.txt |
AC |
77 ms |
25344 KB |
1_14.txt |
AC |
74 ms |
23424 KB |
1_15.txt |
AC |
74 ms |
22784 KB |
1_16.txt |
AC |
73 ms |
23936 KB |
1_17.txt |
AC |
87 ms |
24832 KB |
1_18.txt |
AC |
76 ms |
22016 KB |
1_19.txt |
AC |
70 ms |
22016 KB |
1_20.txt |
AC |
80 ms |
22016 KB |
1_21.txt |
AC |
78 ms |
22528 KB |
1_22.txt |
AC |
82 ms |
22272 KB |
1_23.txt |
AC |
81 ms |
22144 KB |
1_24.txt |
AC |
71 ms |
22528 KB |
1_25.txt |
AC |
74 ms |
23424 KB |
1_26.txt |
AC |
85 ms |
22144 KB |
1_27.txt |
AC |
75 ms |
22400 KB |
1_28.txt |
AC |
75 ms |
22656 KB |
1_29.txt |
AC |
80 ms |
23808 KB |
2_00.txt |
AC |
6 ms |
16640 KB |
2_01.txt |
AC |
89 ms |
28800 KB |
2_02.txt |
AC |
81 ms |
27776 KB |
2_03.txt |
AC |
86 ms |
27392 KB |
2_04.txt |
AC |
82 ms |
25472 KB |
2_05.txt |
AC |
78 ms |
25600 KB |
2_06.txt |
AC |
84 ms |
26112 KB |
2_07.txt |
AC |
83 ms |
22016 KB |
2_08.txt |
AC |
79 ms |
22016 KB |
2_09.txt |
AC |
79 ms |
22016 KB |
2_10.txt |
AC |
73 ms |
22400 KB |
2_11.txt |
AC |
67 ms |
22400 KB |
2_12.txt |
AC |
72 ms |
22400 KB |
2_13.txt |
AC |
65 ms |
22784 KB |
2_14.txt |
AC |
59 ms |
22784 KB |
2_15.txt |
AC |
67 ms |
22784 KB |
2_16.txt |
AC |
75 ms |
22016 KB |
2_17.txt |
AC |
73 ms |
22016 KB |
2_18.txt |
AC |
79 ms |
22016 KB |
2_19.txt |
AC |
76 ms |
22016 KB |
2_20.txt |
AC |
78 ms |
22016 KB |
2_21.txt |
AC |
73 ms |
22016 KB |
2_22.txt |
AC |
74 ms |
22528 KB |
2_23.txt |
AC |
76 ms |
22912 KB |
2_24.txt |
AC |
76 ms |
22784 KB |
2_25.txt |
AC |
80 ms |
25856 KB |
2_26.txt |
AC |
81 ms |
25088 KB |
2_27.txt |
AC |
81 ms |
25728 KB |
2_28.txt |
AC |
78 ms |
24704 KB |
2_29.txt |
AC |
81 ms |
28032 KB |
2_30.txt |
AC |
79 ms |
27008 KB |
2_31.txt |
AC |
83 ms |
24832 KB |
2_32.txt |
AC |
73 ms |
22144 KB |
2_33.txt |
AC |
75 ms |
23552 KB |
2_34.txt |
AC |
78 ms |
24576 KB |
2_35.txt |
AC |
81 ms |
26368 KB |
2_36.txt |
AC |
75 ms |
22016 KB |
2_37.txt |
AC |
77 ms |
22016 KB |
2_38.txt |
AC |
83 ms |
22656 KB |
2_39.txt |
AC |
96 ms |
22144 KB |
2_40.txt |
AC |
84 ms |
22272 KB |
2_41.txt |
AC |
76 ms |
22016 KB |
2_42.txt |
AC |
101 ms |
22400 KB |
2_43.txt |
AC |
74 ms |
25472 KB |
2_44.txt |
AC |
69 ms |
22400 KB |
2_45.txt |
AC |
81 ms |
22656 KB |
2_46.txt |
AC |
88 ms |
22784 KB |
2_47.txt |
AC |
76 ms |
24320 KB |