Submission #8312063


Source Code Expand

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 266666;
int n,d[N],tot,dis[N],Fa[N],dep[N],q[N],dp[N],f[N],sz[N],val[N];Vi e[N];bool mrk[N],gg[N];
Vi dot[N];
void dfs1(int u, int fa, int Dep){
	sz[u]=mrk[u];dep[u]=Dep;dot[Dep].pb(u);Fa[u]=fa;
	rep(i,0,SZ(e[u])-1)if(e[u][i]!=fa)
		dfs1(e[u][i],u,Dep+1),sz[u]+=sz[e[u][i]];
}
void dfs2(int u, int fa){
	f[u]=val[u];
	rep(i,0,SZ(e[u])-1)if(e[u][i]!=fa)
		dfs2(e[u][i],u),umin(f[u],val[u]+f[e[u][i]]);
}
void dfs(int u, int fa){
	int mn=1e9,mn1=1e9;
	rep(i,0,SZ(e[u])-1)if(e[u][i]!=fa)
		if(f[e[u][i]]+val[u]<mn)mn1=mn,mn=f[e[u][i]]+val[u];
		else if(f[e[u][i]]+val[u]<mn1)mn1=f[e[u][i]]+val[u];
	rep(i,0,SZ(e[u])-1)if(e[u][i]!=fa)
		dp[e[u][i]]=val[e[u][i]]+min(dp[u],(mn==f[e[u][i]]+val[u]?mn1:mn));
	rep(i,0,SZ(e[u])-1)if(e[u][i]!=fa)dfs(e[u][i],u);
}
int main() {
	read(n);rep(i,1,n-1){
		int u,v;read(u);read(v);e[u].pb(v);e[v].pb(u);
	}
	static char S[N];scanf("%s",S+1);
	rep(i,1,n)if(S[i]=='W')d[i]^=1,mrk[i]=1,tot++;
	if(!tot){puts("0");return 0;}
	dfs1(1,0,0);rep(i,1,n)gg[i]=sz[i]==0||sz[i]==tot;
	bool find=0;
	per(i,n,0)rep(j,0,SZ(dot[i])-1)if(sz[dot[i][j]]==tot&&!find){
		find=1;gg[dot[i][j]]=0;
	}
	int res=1e9,rt=0;
	rep(i,1,n)if(Fa[i]&&!gg[i])d[i]^=1,d[Fa[i]]^=1;
	per(i,n,1)if(!gg[i])val[i]=(d[i]?-1:1)-1,dp[i]=val[i],rt=i;
	dfs2(rt,0);dfs(rt,0);
//	cerr<<rt<<endl;
//	rep(i,1,n)if(!gg[i])printf("%d:%d %d %d %d\n",i,val[i],dp[i],f[i],d[i]);
	rep(i,1,n)if(!gg[i])umin(res,1-(d[i]?-1:1)+min(dp[i],f[i]));
	rep(i,1,n)if(!gg[i])res+=d[i],res+=2;res-=2;cout<<res<<endl;
	return 0;
}

Submission Info

Submission Time
Task F - Monochrome Cat
User supy
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2373 Byte
Status WA
Exec Time 63 ms
Memory 35584 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:51:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  static char S[N];scanf("%s",S+1);
                                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 4
AC × 90
WA × 28
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt, 1_064.txt, 1_065.txt, 1_066.txt, 1_067.txt, 1_068.txt, 1_069.txt, 1_070.txt, 1_071.txt, 1_072.txt, 1_073.txt, 1_074.txt, 1_075.txt, 1_076.txt, 1_077.txt, 1_078.txt, 1_079.txt, 1_080.txt, 1_081.txt, 1_082.txt, 1_083.txt, 1_084.txt, 1_085.txt, 1_086.txt, 1_087.txt, 1_088.txt, 1_089.txt, 1_090.txt, 1_091.txt, 1_092.txt, 1_093.txt, 1_094.txt, 1_095.txt, 1_096.txt, 1_097.txt, 1_098.txt, 1_099.txt, 1_100.txt, 1_101.txt, 1_102.txt, 1_103.txt, 1_104.txt, 1_105.txt, 1_106.txt, 1_107.txt, 1_108.txt, 1_109.txt, 1_110.txt, 1_111.txt, 1_112.txt, 1_113.txt, 1_114.txt, 1_115.txt, 1_116.txt
Case Name Status Exec Time Memory
0_000.txt AC 8 ms 22784 KB
0_001.txt AC 8 ms 22784 KB
0_002.txt AC 6 ms 16640 KB
0_003.txt AC 7 ms 22784 KB
1_003.txt AC 7 ms 22784 KB
1_004.txt AC 8 ms 22784 KB
1_005.txt AC 6 ms 16640 KB
1_006.txt AC 7 ms 22784 KB
1_007.txt WA 7 ms 22784 KB
1_008.txt AC 7 ms 22784 KB
1_009.txt AC 7 ms 22784 KB
1_010.txt AC 7 ms 22784 KB
1_011.txt AC 6 ms 16640 KB
1_012.txt AC 7 ms 22784 KB
1_013.txt AC 7 ms 22784 KB
1_014.txt WA 7 ms 22784 KB
1_015.txt AC 7 ms 22784 KB
1_016.txt AC 7 ms 22784 KB
1_017.txt AC 6 ms 16640 KB
1_018.txt WA 7 ms 22784 KB
1_019.txt AC 7 ms 22784 KB
1_020.txt AC 6 ms 16640 KB
1_021.txt AC 8 ms 22784 KB
1_022.txt WA 7 ms 22784 KB
1_023.txt AC 6 ms 16640 KB
1_024.txt WA 8 ms 22784 KB
1_025.txt AC 8 ms 22784 KB
1_026.txt WA 7 ms 22784 KB
1_027.txt AC 7 ms 22784 KB
1_028.txt AC 8 ms 22784 KB
1_029.txt AC 6 ms 16640 KB
1_030.txt WA 8 ms 22784 KB
1_031.txt AC 7 ms 22784 KB
1_032.txt WA 7 ms 22784 KB
1_033.txt AC 7 ms 22784 KB
1_034.txt AC 7 ms 22784 KB
1_035.txt AC 6 ms 16640 KB
1_036.txt WA 7 ms 22784 KB
1_037.txt AC 8 ms 22784 KB
1_038.txt WA 7 ms 22784 KB
1_039.txt AC 8 ms 22784 KB
1_040.txt WA 7 ms 22784 KB
1_041.txt AC 6 ms 16640 KB
1_042.txt AC 7 ms 22784 KB
1_043.txt AC 7 ms 22784 KB
1_044.txt AC 7 ms 22784 KB
1_045.txt AC 24 ms 26752 KB
1_046.txt AC 29 ms 28672 KB
1_047.txt AC 30 ms 19712 KB
1_048.txt WA 47 ms 31360 KB
1_049.txt AC 43 ms 30208 KB
1_050.txt AC 40 ms 29952 KB
1_051.txt AC 28 ms 26232 KB
1_052.txt AC 13 ms 23680 KB
1_053.txt AC 23 ms 19576 KB
1_054.txt WA 16 ms 24316 KB
1_055.txt AC 28 ms 26104 KB
1_056.txt WA 20 ms 24700 KB
1_057.txt AC 8 ms 22912 KB
1_058.txt AC 29 ms 25856 KB
1_059.txt AC 15 ms 17664 KB
1_060.txt WA 43 ms 28160 KB
1_061.txt AC 48 ms 28544 KB
1_062.txt AC 29 ms 26240 KB
1_063.txt AC 26 ms 25156 KB
1_064.txt WA 22 ms 24448 KB
1_065.txt AC 7 ms 16768 KB
1_066.txt WA 34 ms 26108 KB
1_067.txt AC 13 ms 23552 KB
1_068.txt WA 25 ms 24832 KB
1_069.txt AC 17 ms 23680 KB
1_070.txt AC 26 ms 24576 KB
1_071.txt AC 27 ms 19200 KB
1_072.txt WA 27 ms 24704 KB
1_073.txt AC 11 ms 23168 KB
1_074.txt AC 9 ms 23040 KB
1_075.txt AC 24 ms 24320 KB
1_076.txt AC 49 ms 26496 KB
1_077.txt AC 26 ms 19200 KB
1_078.txt WA 19 ms 23936 KB
1_079.txt AC 24 ms 24448 KB
1_080.txt AC 33 ms 24576 KB
1_081.txt AC 60 ms 31872 KB
1_082.txt AC 62 ms 32256 KB
1_083.txt AC 30 ms 19712 KB
1_084.txt WA 61 ms 34176 KB
1_085.txt AC 63 ms 35200 KB
1_086.txt AC 63 ms 35584 KB
1_087.txt AC 35 ms 27000 KB
1_088.txt AC 37 ms 27000 KB
1_089.txt AC 25 ms 20088 KB
1_090.txt WA 35 ms 27000 KB
1_091.txt AC 36 ms 27000 KB
1_092.txt AC 26 ms 20088 KB
1_093.txt AC 58 ms 29312 KB
1_094.txt AC 60 ms 31232 KB
1_095.txt AC 30 ms 19712 KB
1_096.txt WA 58 ms 30336 KB
1_097.txt AC 58 ms 30208 KB
1_098.txt AC 59 ms 30720 KB
1_099.txt AC 41 ms 26748 KB
1_100.txt AC 42 ms 26748 KB
1_101.txt AC 28 ms 19964 KB
1_102.txt WA 41 ms 26748 KB
1_103.txt AC 41 ms 26748 KB
1_104.txt WA 43 ms 26748 KB
1_105.txt AC 49 ms 26496 KB
1_106.txt WA 49 ms 26496 KB
1_107.txt AC 30 ms 19840 KB
1_108.txt WA 48 ms 26624 KB
1_109.txt AC 48 ms 26496 KB
1_110.txt AC 51 ms 26496 KB
1_111.txt AC 49 ms 26624 KB
1_112.txt AC 49 ms 26624 KB
1_113.txt AC 30 ms 19840 KB
1_114.txt WA 48 ms 26496 KB
1_115.txt AC 47 ms 26624 KB
1_116.txt AC 50 ms 26496 KB