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 |
|
|
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 |