Submission #1693884


Source Code Expand

#include<bits/stdc++.h>
#define inf 1000000000
#define N 200009
using namespace std;

int n,tot,cnt,tp,dfsclk,q[N],fst[N],pnt[N<<1],nxt[N<<1];
int lf[N],rg[N],id[N],anc[N],sz[N],son[N],fa[N],d[N],f[N];
long long ans; char s[N];
struct node{ int x,y; }a[N],b[N],c[N];
bool operator <(node u,node v){ return u.x<v.x; }
void mdy(node &u,node v){
	u.x=max(u.x,v.x); u.y=min(u.y,v.y);
}
void add(int x,int y){
	pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot;
}
int find(int x,int y){
	int t=x;
	for (; anc[x]!=anc[y]; x=fa[anc[x]]) t=anc[x];
	return x==y?t:id[lf[y]+1];
}
void calc(int x){
	int i,y;
	if (b[x].x) c[cnt=1]=b[x]; else cnt=0;
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) c[++cnt]=a[y];
	}
	sort(c+1,c+cnt+1);
	int l=0,r=c[cnt].x-1;
	if (b[x].x==c[cnt].x) r=min(r,a[x].x);
	else{
		for (i=fst[x]; i; i=nxt[i]){
			y=pnt[i];
			if (y!=fa[x] && c[cnt].x==a[y].x){
				r=min(r,b[y].x); break;
			}
		}
	}
	cout<<x<<endl;
	if (s[x]=='0'){
		l=inf;
		for (i=1; i<=cnt; i++){
			//y=c[i].y;
			//if (!y) continue;
			if (i<cnt && c[i].y<inf) l=min(l,c[cnt-1].x);
			//else l=min(l,c[i].y+c[cnt-1].x+c[i].y);
			//cout<<"?	"<<y<<endl;
			//if (lf[y]<=lf[x] && lf[x]<=rg[y]){
			//	y=find(x,y);
			//	cout<<"	"<<c[i].z<<endl;
			//}
			//else{
			//	cout<<"	"<<c[i].z<<' '<<b[y].x<<endl;
			//	l=min(l,c[i].z+b[y].x-1);
			//}
		}
	}
	cout<<"  "<<l<<' '<<r<<endl;
	ans+=max(0,r-l+1);
}
void dfs(int x){
	int i,y; sz[x]=1;
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]){
			fa[y]=x; d[y]=d[x]+1;
			dfs(y); sz[x]+=sz[y];
			if (sz[y]>sz[son[x]]) son[x]=y;
			mdy(a[x],a[y]);
		}
	}
	a[x].x++; if (s[x]=='1') a[x].y=1;
}
void dvd(int x,int tp){
	int i,y;
	lf[x]=++dfsclk; id[dfsclk]=x; anc[x]=tp;
	if (son[x]) dvd(son[x],tp);
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x] && y!=son[x]) dvd(y,y);
	}
	rg[x]=dfsclk;
}
void dfs2(int x){
	int i,y;
	for (i=fst[x],tp=0; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) q[++tp]=y;
	}
	node tmp=b[x];
	for (i=1; i<=tp; i++){
		y=q[i];
		mdy(b[y],tmp);
		mdy(tmp,a[y]);
	}
	for (i=tp,tmp=(node){-inf,inf}; i; i--){
		y=q[i];
		mdy(b[y],tmp);
		mdy(tmp,a[y]);
	}
	for (i=1; i<=tp; i++){
		b[q[i]].x++; b[q[i]].y++;
	}
	if (s[x]=='1')
		for (i=1; i<=tp; i++){
			b[q[i]].y=1;// b[q[i]].z=1;
		}
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) dfs2(y);
	}
}
int main(){
	scanf("%d",&n);
	int i,x,y;
	for (i=1; i<n; i++){
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	scanf("%s",s+1);
	for (i=1; i<=n; i++) a[i].y=b[i].y=inf;
	dfs(1); dvd(1,1); dfs2(1);
	for (i=1; i<=n; i++) calc(i);
	printf("%lld\n",ans+1);
	return 0;
}

Submission Info

Submission Time
Task F - Black Radius
User lych_cys
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2722 Byte
Status WA
Exec Time 816 ms
Memory 29056 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:115:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:118:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^
./Main.cpp:121:17: 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 0 / 1300 0 / 600
Status
WA × 3
WA × 31
WA × 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 WA 4 ms 14592 KB
0_01.txt WA 4 ms 14592 KB
0_02.txt WA 4 ms 14592 KB
1_00.txt WA 4 ms 14592 KB
1_01.txt WA 747 ms 27776 KB
1_02.txt WA 756 ms 24320 KB
1_03.txt WA 733 ms 17920 KB
1_04.txt WA 737 ms 18304 KB
1_05.txt WA 699 ms 19328 KB
1_06.txt WA 746 ms 17536 KB
1_07.txt WA 720 ms 17536 KB
1_08.txt WA 743 ms 18304 KB
1_09.txt WA 816 ms 23680 KB
1_10.txt WA 728 ms 22016 KB
1_11.txt WA 736 ms 27648 KB
1_12.txt WA 724 ms 19840 KB
1_13.txt WA 743 ms 22272 KB
1_14.txt WA 754 ms 19584 KB
1_15.txt WA 771 ms 18688 KB
1_16.txt WA 744 ms 20480 KB
1_17.txt WA 749 ms 23424 KB
1_18.txt WA 734 ms 17664 KB
1_19.txt WA 730 ms 17536 KB
1_20.txt WA 735 ms 17920 KB
1_21.txt WA 765 ms 18432 KB
1_22.txt WA 710 ms 17920 KB
1_23.txt WA 733 ms 17792 KB
1_24.txt WA 717 ms 18304 KB
1_25.txt WA 807 ms 19584 KB
1_26.txt WA 712 ms 17792 KB
1_27.txt WA 737 ms 18176 KB
1_28.txt WA 723 ms 18816 KB
1_29.txt WA 733 ms 20352 KB
2_00.txt WA 4 ms 14592 KB
2_01.txt WA 740 ms 29056 KB
2_02.txt WA 764 ms 26752 KB
2_03.txt WA 750 ms 25728 KB
2_04.txt WA 747 ms 24320 KB
2_05.txt WA 746 ms 23808 KB
2_06.txt WA 753 ms 24064 KB
2_07.txt WA 746 ms 19584 KB
2_08.txt WA 743 ms 19584 KB
2_09.txt WA 734 ms 18176 KB
2_10.txt WA 754 ms 20096 KB
2_11.txt WA 733 ms 19968 KB
2_12.txt WA 719 ms 19328 KB
2_13.txt WA 739 ms 20992 KB
2_14.txt WA 717 ms 20992 KB
2_15.txt WA 736 ms 19840 KB
2_16.txt WA 736 ms 19200 KB
2_17.txt WA 724 ms 19200 KB
2_18.txt WA 728 ms 18944 KB
2_19.txt WA 739 ms 19328 KB
2_20.txt WA 770 ms 19200 KB
2_21.txt WA 727 ms 17664 KB
2_22.txt WA 738 ms 19968 KB
2_23.txt WA 736 ms 20352 KB
2_24.txt WA 735 ms 19200 KB
2_25.txt WA 755 ms 24576 KB
2_26.txt WA 757 ms 23296 KB
2_27.txt WA 758 ms 23424 KB
2_28.txt WA 774 ms 23040 KB
2_29.txt WA 764 ms 27008 KB
2_30.txt WA 748 ms 25728 KB
2_31.txt WA 736 ms 23168 KB
2_32.txt WA 746 ms 19456 KB
2_33.txt WA 758 ms 20736 KB
2_34.txt WA 727 ms 22272 KB
2_35.txt WA 724 ms 25344 KB
2_36.txt WA 732 ms 19584 KB
2_37.txt WA 739 ms 18560 KB
2_38.txt WA 740 ms 19712 KB
2_39.txt WA 724 ms 19328 KB
2_40.txt WA 733 ms 19712 KB
2_41.txt WA 740 ms 19072 KB
2_42.txt WA 717 ms 19968 KB
2_43.txt WA 761 ms 24192 KB
2_44.txt WA 715 ms 19968 KB
2_45.txt WA 719 ms 20352 KB
2_46.txt WA 739 ms 20608 KB
2_47.txt WA 717 ms 21376 KB