Submission #1678148
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
inline void judge(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const int maxn=200005;
int head[maxn],t[maxn<<1],ne[maxn<<1],num,n;
int dp[maxn],nr[maxn];
char s[maxn];
i64 ans=0;
inline void dfs1(int x,int f){
dp[x]=0;nr[x]=n;if(s[x]=='1')nr[x]=0;
forE(i,x)if(t[i]!=f){
dfs1(t[i],x);
dp[x]=max(dp[x],dp[t[i]]+1);
nr[x]=min(nr[x],nr[t[i]]+1);
}
}
inline void dfs2(int x,int f,int n1,int dp1){
int maxi1=0,nd1=0,maxi2=0,nd2=0,tot=0,low=n;
maxi1=dp1;nd1=n1;vector<int> son;
if(nd1<n)low=min(low,maxi1);
forE(i,x)if(t[i]!=f){
tot++;son.pb(t[i]);
if(nr[t[i]]!=n)low=min(low,dp[t[i]]+1);
if(dp[t[i]]+1>maxi1){
maxi2=maxi1;nd2=nd1;
maxi1=dp[t[i]]+1;nd1=nr[t[i]]+1;
}else if (dp[t[i]]+1>maxi2){
maxi2=dp[t[i]]+1;nd2=nr[t[i]]+1;
}
}if(s[x]=='1')low=0;
ans+=max(0,min(maxi1-1,maxi2+1)-low+1);
vector<int> dpprmax(tot+2,0),dpsfmax(tot+2,0),nrprmin(tot+2,n),nrsfmin(tot+2,n);
rep(i,1,tot){
dpprmax[i]=max(dpprmax[i-1],dp[son[i-1]]+2);
nrprmin[i]=min(nrprmin[i-1],nr[son[i-1]]+2);
}
per(i,tot,1){
dpsfmax[i]=max(dpsfmax[i+1],dp[son[i-1]]+2);
nrsfmin[i]=min(nrsfmin[i+1],nr[son[i-1]]+2);
}if(s[x]=='1')n1=0;
rep(i,1,tot){
dfs2(son[i-1],x,min(n1+1,min(nrprmin[i-1],nrsfmin[i+1])),max(max(dp1+1,dpprmax[i-1]),dpsfmax[i+1]));
}
}
inline void addedge(int x,int y){
ne[++num]=head[x];head[x]=num;t[num]=y;
ne[++num]=head[y];head[y]=num;t[num]=x;
}
int main(){
read(n);
rep(i,1,n)head[i]=-1;
rep(i,1,n-1){
int x,y;read(x);read(y);
addedge(x,y);
}scanf("%s",s+1);
dfs1(1,-1);
dfs2(1,-1,n,0);
ans++;
printf("%lld\n",ans);
return 0;
}
Submission Info
Submission Time
2017-10-12 19:18:37+0900
Task
F - Black Radius
User
Scape
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
2478 Byte
Status
AC
Exec Time
148 ms
Memory
51200 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:82:18: 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
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
2 ms
2304 KB
0_01.txt
AC
2 ms
2304 KB
0_02.txt
AC
2 ms
2304 KB
1_00.txt
AC
2 ms
2304 KB
1_01.txt
AC
146 ms
51200 KB
1_02.txt
AC
134 ms
35072 KB
1_03.txt
AC
99 ms
6144 KB
1_04.txt
AC
76 ms
7928 KB
1_05.txt
AC
61 ms
9972 KB
1_06.txt
AC
92 ms
5888 KB
1_07.txt
AC
92 ms
6016 KB
1_08.txt
AC
96 ms
9856 KB
1_09.txt
AC
122 ms
28544 KB
1_10.txt
AC
119 ms
25344 KB
1_11.txt
AC
138 ms
50944 KB
1_12.txt
AC
101 ms
16640 KB
1_13.txt
AC
126 ms
26880 KB
1_14.txt
AC
100 ms
14976 KB
1_15.txt
AC
98 ms
10752 KB
1_16.txt
AC
116 ms
18432 KB
1_17.txt
AC
120 ms
23808 KB
1_18.txt
AC
96 ms
6016 KB
1_19.txt
AC
94 ms
6016 KB
1_20.txt
AC
98 ms
6528 KB
1_21.txt
AC
104 ms
9088 KB
1_22.txt
AC
89 ms
7292 KB
1_23.txt
AC
93 ms
6912 KB
1_24.txt
AC
102 ms
9344 KB
1_25.txt
AC
93 ms
14456 KB
1_26.txt
AC
86 ms
6784 KB
1_27.txt
AC
85 ms
7800 KB
1_28.txt
AC
74 ms
9848 KB
1_29.txt
AC
109 ms
16076 KB
2_00.txt
AC
2 ms
2304 KB
2_01.txt
AC
148 ms
49280 KB
2_02.txt
AC
148 ms
42368 KB
2_03.txt
AC
141 ms
40064 KB
2_04.txt
AC
147 ms
27776 KB
2_05.txt
AC
143 ms
28544 KB
2_06.txt
AC
135 ms
31872 KB
2_07.txt
AC
115 ms
6144 KB
2_08.txt
AC
99 ms
6144 KB
2_09.txt
AC
99 ms
6144 KB
2_10.txt
AC
75 ms
7928 KB
2_11.txt
AC
77 ms
7928 KB
2_12.txt
AC
77 ms
7928 KB
2_13.txt
AC
62 ms
9972 KB
2_14.txt
AC
72 ms
9972 KB
2_15.txt
AC
67 ms
9972 KB
2_16.txt
AC
94 ms
5888 KB
2_17.txt
AC
100 ms
5888 KB
2_18.txt
AC
100 ms
5888 KB
2_19.txt
AC
93 ms
6016 KB
2_20.txt
AC
92 ms
6016 KB
2_21.txt
AC
96 ms
6016 KB
2_22.txt
AC
98 ms
9472 KB
2_23.txt
AC
102 ms
11776 KB
2_24.txt
AC
104 ms
11008 KB
2_25.txt
AC
125 ms
30208 KB
2_26.txt
AC
124 ms
25600 KB
2_27.txt
AC
123 ms
29952 KB
2_28.txt
AC
113 ms
23424 KB
2_29.txt
AC
147 ms
43904 KB
2_30.txt
AC
138 ms
37504 KB
2_31.txt
AC
127 ms
24064 KB
2_32.txt
AC
94 ms
7296 KB
2_33.txt
AC
105 ms
15488 KB
2_34.txt
AC
118 ms
22656 KB
2_35.txt
AC
138 ms
33408 KB
2_36.txt
AC
98 ms
6016 KB
2_37.txt
AC
96 ms
6144 KB
2_38.txt
AC
100 ms
10496 KB
2_39.txt
AC
99 ms
6784 KB
2_40.txt
AC
80 ms
7416 KB
2_41.txt
AC
89 ms
6400 KB
2_42.txt
AC
76 ms
7928 KB
2_43.txt
AC
120 ms
27904 KB
2_44.txt
AC
76 ms
7928 KB
2_45.txt
AC
66 ms
9204 KB
2_46.txt
AC
69 ms
9972 KB
2_47.txt
AC
98 ms
18688 KB