Submission #1690801


Source Code Expand

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
int n,f[200010],g[200010];
char s[200010];
vector<int> a[200010];
long long p=1;
inline void dp(int i,int j)
{
	int k;
	f[i]=1;
	g[i]=s[i-1]-'0';
	for(k=0;k<a[i].size();k++)
	  if(a[i][k]!=j)
	    {
		 dp(a[i][k],i);
		 f[i]=max(f[i],f[a[i][k]]+1);
		 g[i]+=g[a[i][k]];
		}
}
inline void dp2(int i,int j,int b,int c)
{
	int k,u,v,w,d=0;
	if(i==1)
	  u=v=w=0;
	else
	  {
	   u=b;
	   v=0;
	   if(c)
	     w=b;
	  }
	b++;
	c+=s[i-1]-'0';
	for(k=0;k<a[i].size();k++)
	  if(a[i][k]!=j)
	    {
	     if(f[a[i][k]]>u)
	       v=u,u=f[a[i][k]];
	     else
	       v=max(v,f[a[i][k]]);
	     if(g[i])
	       w=min(w,f[a[i][k]]);
	     if(f[a[i][k]]+1>b)
	       d=b,b=f[a[i][k]]+1;
	     else
	       d=max(d,f[a[i][k]]+1);
	     c+=g[a[i][k]];
		}
	u=min(u-1,v+1);
	if(s[i-1]=='1')
	  w=0;
	p+=max(u-w+1,0);
	for(k=0,u=b,v=c;k<a[i].size();k++)
	  if(a[i][k]!=j)
	    dp2(a[i][k],i,(f[a[i][k]]+1==b)?d:b,c-g[a[i][k]]);
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	  {
	   scanf("%d%d",&j,&k);
	   a[j].push_back(k);
	   a[k].push_back(j);
	  }
	scanf("%s",&s);
	dp(1,0);
	dp2(1,0,0,0);
	cout<<p<<"\n";
	return 0;
}

Submission Info

Submission Time
Task F - Black Radius
User fateice
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1416 Byte
Status WA
Exec Time 129 ms
Memory 20736 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:75:15: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[200010]’ [-Wformat=]
  scanf("%s",&s);
               ^
./Main.cpp:68:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:71:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&j,&k);
                        ^
./Main.cpp:75:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",&s);
                ^

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 1300 / 1300 0 / 600
Status
AC × 3
AC × 31
AC × 36
WA × 45
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 3 ms 6400 KB
0_01.txt AC 3 ms 6400 KB
0_02.txt AC 3 ms 6400 KB
1_00.txt AC 3 ms 6400 KB
1_01.txt AC 121 ms 20736 KB
1_02.txt AC 112 ms 17920 KB
1_03.txt AC 104 ms 12928 KB
1_04.txt AC 85 ms 13304 KB
1_05.txt AC 69 ms 13684 KB
1_06.txt AC 108 ms 13312 KB
1_07.txt AC 101 ms 13184 KB
1_08.txt AC 103 ms 13824 KB
1_09.txt AC 107 ms 16896 KB
1_10.txt AC 103 ms 16256 KB
1_11.txt AC 121 ms 20608 KB
1_12.txt AC 103 ms 14720 KB
1_13.txt AC 119 ms 16512 KB
1_14.txt AC 108 ms 14592 KB
1_15.txt AC 129 ms 13952 KB
1_16.txt AC 102 ms 15104 KB
1_17.txt AC 105 ms 16000 KB
1_18.txt AC 101 ms 12928 KB
1_19.txt AC 97 ms 13056 KB
1_20.txt AC 106 ms 12928 KB
1_21.txt AC 129 ms 13440 KB
1_22.txt AC 112 ms 13180 KB
1_23.txt AC 103 ms 13180 KB
1_24.txt AC 111 ms 13696 KB
1_25.txt AC 88 ms 14456 KB
1_26.txt AC 101 ms 13052 KB
1_27.txt AC 82 ms 13304 KB
1_28.txt AC 80 ms 13688 KB
1_29.txt AC 93 ms 14972 KB
2_00.txt WA 3 ms 6400 KB
2_01.txt WA 103 ms 20352 KB
2_02.txt WA 105 ms 19200 KB
2_03.txt AC 105 ms 18816 KB
2_04.txt WA 106 ms 16640 KB
2_05.txt WA 107 ms 16768 KB
2_06.txt WA 106 ms 17408 KB
2_07.txt WA 99 ms 12928 KB
2_08.txt WA 102 ms 12928 KB
2_09.txt WA 100 ms 12928 KB
2_10.txt WA 88 ms 13304 KB
2_11.txt WA 83 ms 13304 KB
2_12.txt AC 87 ms 13304 KB
2_13.txt WA 66 ms 13812 KB
2_14.txt WA 64 ms 13684 KB
2_15.txt AC 68 ms 13684 KB
2_16.txt WA 98 ms 13184 KB
2_17.txt WA 103 ms 13184 KB
2_18.txt WA 107 ms 13184 KB
2_19.txt WA 111 ms 13184 KB
2_20.txt WA 111 ms 13184 KB
2_21.txt WA 106 ms 13184 KB
2_22.txt WA 106 ms 13696 KB
2_23.txt WA 100 ms 14080 KB
2_24.txt WA 102 ms 13952 KB
2_25.txt WA 111 ms 17152 KB
2_26.txt WA 115 ms 16384 KB
2_27.txt WA 107 ms 17152 KB
2_28.txt WA 99 ms 16000 KB
2_29.txt WA 106 ms 19456 KB
2_30.txt WA 103 ms 18304 KB
2_31.txt WA 104 ms 16000 KB
2_32.txt WA 99 ms 13312 KB
2_33.txt WA 99 ms 14720 KB
2_34.txt WA 100 ms 15744 KB
2_35.txt WA 102 ms 17536 KB
2_36.txt WA 100 ms 12928 KB
2_37.txt WA 107 ms 12928 KB
2_38.txt WA 97 ms 13696 KB
2_39.txt WA 97 ms 13056 KB
2_40.txt WA 85 ms 13304 KB
2_41.txt WA 91 ms 13184 KB
2_42.txt WA 80 ms 13176 KB
2_43.txt WA 113 ms 16768 KB
2_44.txt WA 80 ms 13304 KB
2_45.txt WA 71 ms 13560 KB
2_46.txt WA 71 ms 13684 KB
2_47.txt WA 96 ms 15352 KB