Submission #1692364


Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200010
#define inf 2147483647
#define ll long long
#define pa(a, b) (data){a, b}
using namespace std;

struct edge{int x, y, next;}a[N*2];
struct data{int def, sum;}d[N];
int n, l, p[N], x, y, def[N], def1[N], sum[N], def_fa[N], fa[N], mx, mx1, R, L;
ll ans;
char S[N];

inline void add(int x, int y){a[++l].x=x; a[l].y=y; a[l].next=p[x]; p[x]=l;}
inline void dfs(int x){
	def[x]=def1[x]=1; sum[x]=S[x]=='1'?1:0;
	for(int i=p[x]; i; i=a[i].next)if(fa[x]!=a[i].y){
		fa[a[i].y]=x; dfs(a[i].y); sum[x]+=sum[a[i].y];
		if(def[x]<=def[a[i].y]+1){def1[x]=def[x]; def[x]=def[a[i].y]+1;}
		else if(def1[x]<=def[a[i].y]+1)def1[x]=def[a[i].y]+1;
	}
}
inline void dp(int x){
	for(int i=p[x]; i; i=a[i].next)if(fa[x]!=a[i].y){
		if(def[x]==def[a[i].y]+1)def_fa[a[i].y]=max(def_fa[x], def1[x])+1;
		else def_fa[a[i].y]=max(def_fa[x], def[x])+1;
		dp(a[i].y);
	}
}

int main(){
	scanf("%d", &n);
	l=0; memset(p, 0, sizeof(p));
	for(int i=1; i<=n-1; i++){scanf("%d%d", &x, &y); add(x, y); add(y, x);}
	scanf("%s", S+1);
	fa[1]=1; dfs(1);
	def_fa[1]=0; dp(1);
	ans=1; //全集
	for(int i=1; i<=n; i++){
		l=0;
		for(int j=p[i]; j; j=a[j].next)
			if(fa[i]==a[j].y)d[++l]=pa(def_fa[i]-1, sum[1]-sum[i]);
			else d[++l]=pa(def[a[j].y], sum[a[j].y]);
		mx=mx1=0;
		for(int j=1; j<=l; j++)
			if(mx<=d[j].def){mx1=mx; mx=d[j].def;}
			else if(mx1<=d[j].def)mx1=d[j].def;
		R=min(mx1+1, mx-1);
		if(R==-1)continue;
		if(S[i]=='1'){ans+=R+1; continue;}
		L=inf;
		for(int j=1; j<=l; j++)if(d[j].sum)L=min(L, d[j].def);
		if(L<=R)ans+=R-L+1;
	}
	printf("%lld", ans);
	return 0;
}

Submission Info

Submission Time
Task F - Black Radius
User leoly
Language C++14 (GCC 5.4.1)
Score 1900
Code Size 1680 Byte
Status AC
Exec Time 91 ms
Memory 14720 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:34:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:36:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n-1; i++){scanf("%d%d", &x, &y); add(x, y); add(y, x);}
                                                 ^
./Main.cpp:37: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
AC × 3
AC × 31
AC × 81
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 6272 KB
0_01.txt AC 2 ms 6272 KB
0_02.txt AC 2 ms 6272 KB
1_00.txt AC 2 ms 6272 KB
1_01.txt AC 75 ms 14720 KB
1_02.txt AC 69 ms 13568 KB
1_03.txt AC 64 ms 11264 KB
1_04.txt AC 54 ms 11264 KB
1_05.txt AC 51 ms 11264 KB
1_06.txt AC 63 ms 11264 KB
1_07.txt AC 63 ms 11264 KB
1_08.txt AC 65 ms 11520 KB
1_09.txt AC 68 ms 13056 KB
1_10.txt AC 71 ms 12672 KB
1_11.txt AC 69 ms 14592 KB
1_12.txt AC 63 ms 11904 KB
1_13.txt AC 67 ms 12928 KB
1_14.txt AC 64 ms 11904 KB
1_15.txt AC 64 ms 11648 KB
1_16.txt AC 66 ms 12160 KB
1_17.txt AC 66 ms 12672 KB
1_18.txt AC 63 ms 11264 KB
1_19.txt AC 63 ms 11264 KB
1_20.txt AC 63 ms 11264 KB
1_21.txt AC 64 ms 11520 KB
1_22.txt AC 58 ms 11264 KB
1_23.txt AC 59 ms 11264 KB
1_24.txt AC 63 ms 11520 KB
1_25.txt AC 58 ms 11776 KB
1_26.txt AC 59 ms 11136 KB
1_27.txt AC 58 ms 11264 KB
1_28.txt AC 56 ms 11392 KB
1_29.txt AC 62 ms 12032 KB
2_00.txt AC 2 ms 6272 KB
2_01.txt AC 69 ms 14592 KB
2_02.txt AC 68 ms 14080 KB
2_03.txt AC 69 ms 13952 KB
2_04.txt AC 91 ms 12928 KB
2_05.txt AC 69 ms 13056 KB
2_06.txt AC 69 ms 13312 KB
2_07.txt AC 64 ms 11264 KB
2_08.txt AC 66 ms 11264 KB
2_09.txt AC 65 ms 11264 KB
2_10.txt AC 54 ms 11264 KB
2_11.txt AC 54 ms 11264 KB
2_12.txt AC 59 ms 11264 KB
2_13.txt AC 53 ms 11264 KB
2_14.txt AC 51 ms 11264 KB
2_15.txt AC 51 ms 11264 KB
2_16.txt AC 64 ms 11264 KB
2_17.txt AC 64 ms 11264 KB
2_18.txt AC 65 ms 11264 KB
2_19.txt AC 64 ms 11264 KB
2_20.txt AC 69 ms 11264 KB
2_21.txt AC 65 ms 11264 KB
2_22.txt AC 66 ms 11520 KB
2_23.txt AC 66 ms 11776 KB
2_24.txt AC 67 ms 11648 KB
2_25.txt AC 71 ms 13184 KB
2_26.txt AC 69 ms 12800 KB
2_27.txt AC 70 ms 13056 KB
2_28.txt AC 66 ms 12544 KB
2_29.txt AC 72 ms 14208 KB
2_30.txt AC 68 ms 13696 KB
2_31.txt AC 68 ms 12672 KB
2_32.txt AC 65 ms 11392 KB
2_33.txt AC 66 ms 12032 KB
2_34.txt AC 67 ms 12416 KB
2_35.txt AC 66 ms 13312 KB
2_36.txt AC 64 ms 11264 KB
2_37.txt AC 65 ms 11264 KB
2_38.txt AC 66 ms 11520 KB
2_39.txt AC 65 ms 11392 KB
2_40.txt AC 57 ms 11264 KB
2_41.txt AC 62 ms 11264 KB
2_42.txt AC 53 ms 11136 KB
2_43.txt AC 66 ms 12928 KB
2_44.txt AC 58 ms 11264 KB
2_45.txt AC 54 ms 11264 KB
2_46.txt AC 54 ms 11264 KB
2_47.txt AC 62 ms 12160 KB