AtCoder Regular Contest 097

Submission #3967485

Source codeソースコード

/* --- author: dxm --- */
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

#define INF 1e9
#define Inf 1e18
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

void qread(int &x){
	int neg=1;x=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')neg=-1;c=getchar();}
	while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
	x*=neg;
}

const int maxn=100005;
int n,rt,m,cnt;
int a[maxn],dp[maxn][2],dp2[maxn],d[maxn];
bool exi[maxn];
vector<int>edge[maxn];
char c[maxn];

void dfs1(int x,int p){
	if(c[x]=='W')exi[x]=true;
	rep(i,edge[x].size()){
		int y=edge[x][i];
		if(y==p)continue;
		dfs1(y,x);
		exi[x]|=exi[y];
		if(exi[y])d[x]++;
	}
	if(!exi[x])m--;
} 

void dfs2(int x,int p){
	dp[x][0]=-INF;
	dp[x][1]=dp2[x]=1+a[x];
	bool leaf=true;
	rep(i,edge[x].size()){
		int y=edge[x][i];
		if(y==p||!exi[y])continue;
		leaf=false;
		dfs2(y,x);
		dp2[x]=max(dp2[x],dp2[y]);
		dp2[x]=max(dp2[x],dp[x][0]+dp[y][1]);
		dp2[x]=max(dp2[x],dp[x][1]+max(dp[y][0],dp[y][1]));
		dp[x][0]=max(dp[x][0],dp[y][0]+a[x]+1);
		dp[x][1]=max(dp[x][1],dp[y][1]+a[x]+1);
	}
	if(leaf)dp[x][0]=1+a[x],dp[x][1]=-INF;
	dp2[x]=max(dp2[x],max(dp[x][0],dp[x][1]));
}

int main(){
#ifdef FILE
	freopen("FILE.in","r",stdin);
	freopen("FILE.out","w",stdout);
#endif
	scanf("%d",&n);
	m=n;
	REP(i,n-1){
		int u,v;
		scanf("%d%d",&u,&v);
		edge[u].pb(v);
		edge[v].pb(u);
	}
	scanf("%s",c+1);
	REP(i,n)if(c[i]=='W')cnt++,rt=i;
	if(!cnt){
		puts("0");
		return 0;
	}
	if(cnt==1){
		puts("0");
		return 0;
	}
	dfs1(rt,0);
	int ans=(m-1)*2;
	REP(i,n)if(exi[i]){
		a[i]=(c[i]=='W')^((d[i]+(i!=rt))&1);
		ans+=a[i];
		if(!a[i])a[i]=-1;
	}
	dfs2(rt,0);
	printf("%d\n",ans-dp2[rt]);
#ifdef TIME
	printf("Running Time = %d ms\n",int(clock()*1000.0/CLOCKS_PER_SEC));
#endif
	return 0;
}

/*
Input:
-----------------
Output:
*/

Submission

Task問題 F - Monochrome Cat
User nameユーザ名 little_waxberry
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 2212 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:73:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:77:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
^
./Main.cpp:81:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",c+1);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_000.txt,0_001.txt,0_002.txt,0_003.txt
All 0 / 800 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_000.txt AC 3 ms 4224 KB
0_001.txt AC 3 ms 4224 KB
0_002.txt AC 3 ms 4224 KB
0_003.txt AC 3 ms 4224 KB
1_003.txt WA
1_004.txt WA
1_005.txt AC 3 ms 4224 KB
1_006.txt WA
1_007.txt WA
1_008.txt AC 3 ms 4224 KB
1_009.txt AC 3 ms 4224 KB
1_010.txt AC 3 ms 4224 KB
1_011.txt AC 3 ms 4224 KB
1_012.txt WA
1_013.txt AC 3 ms 4224 KB
1_014.txt AC 3 ms 4224 KB
1_015.txt AC 3 ms 4224 KB
1_016.txt AC 3 ms 4224 KB
1_017.txt AC 3 ms 4224 KB
1_018.txt WA
1_019.txt AC 3 ms 4224 KB
1_020.txt AC 3 ms 4224 KB
1_021.txt AC 3 ms 4224 KB
1_022.txt AC 3 ms 4224 KB
1_023.txt AC 3 ms 4224 KB
1_024.txt WA
1_025.txt AC 3 ms 4224 KB
1_026.txt AC 3 ms 4224 KB
1_027.txt AC 3 ms 4224 KB
1_028.txt AC 3 ms 4224 KB
1_029.txt AC 3 ms 4224 KB
1_030.txt WA
1_031.txt AC 3 ms 4224 KB
1_032.txt AC 3 ms 4224 KB
1_033.txt AC 3 ms 4224 KB
1_034.txt AC 3 ms 4224 KB
1_035.txt AC 3 ms 4224 KB
1_036.txt WA
1_037.txt AC 3 ms 4224 KB
1_038.txt AC 3 ms 4224 KB
1_039.txt AC 3 ms 4224 KB
1_040.txt AC 3 ms 4224 KB
1_041.txt AC 3 ms 4224 KB
1_042.txt WA
1_043.txt AC 3 ms 4224 KB
1_044.txt AC 3 ms 4224 KB
1_045.txt AC 19 ms 6912 KB
1_046.txt AC 23 ms 7680 KB
1_047.txt AC 34 ms 7424 KB
1_048.txt WA
1_049.txt AC 38 ms 12288 KB
1_050.txt AC 33 ms 9856 KB
1_051.txt AC 25 ms 7288 KB
1_052.txt AC 8 ms 4992 KB
1_053.txt AC 24 ms 7288 KB
1_054.txt WA
1_055.txt AC 25 ms 7288 KB
1_056.txt WA
1_057.txt AC 4 ms 4352 KB
1_058.txt AC 24 ms 7552 KB
1_059.txt AC 14 ms 5376 KB
1_060.txt WA
1_061.txt AC 44 ms 10368 KB
1_062.txt AC 23 ms 7424 KB
1_063.txt AC 25 ms 6528 KB
1_064.txt AC 18 ms 5888 KB
1_065.txt AC 5 ms 4480 KB
1_066.txt WA
1_067.txt AC 10 ms 4992 KB
1_068.txt AC 21 ms 6144 KB
1_069.txt AC 13 ms 5248 KB
1_070.txt AC 23 ms 6016 KB
1_071.txt AC 30 ms 6912 KB
1_072.txt WA
1_073.txt AC 6 ms 4608 KB
1_074.txt AC 5 ms 4480 KB
1_075.txt AC 21 ms 5760 KB
1_076.txt AC 46 ms 7808 KB
1_077.txt AC 29 ms 6912 KB
1_078.txt WA
1_079.txt AC 20 ms 5760 KB
1_080.txt AC 22 ms 6016 KB
1_081.txt AC 52 ms 12032 KB
1_082.txt AC 55 ms 13312 KB
1_083.txt AC 35 ms 7424 KB
1_084.txt WA
1_085.txt AC 57 ms 15616 KB
1_086.txt AC 54 ms 15232 KB
1_087.txt AC 32 ms 8312 KB
1_088.txt AC 36 ms 8312 KB
1_089.txt AC 29 ms 7800 KB
1_090.txt WA
1_091.txt AC 32 ms 8312 KB
1_092.txt AC 28 ms 7800 KB
1_093.txt AC 50 ms 10112 KB
1_094.txt AC 50 ms 10368 KB
1_095.txt AC 35 ms 7424 KB
1_096.txt WA
1_097.txt AC 50 ms 10112 KB
1_098.txt AC 49 ms 10112 KB
1_099.txt AC 41 ms 8060 KB
1_100.txt AC 41 ms 8060 KB
1_101.txt AC 33 ms 7676 KB
1_102.txt WA
1_103.txt AC 41 ms 8060 KB
1_104.txt AC 40 ms 8060 KB
1_105.txt AC 47 ms 7936 KB
1_106.txt AC 47 ms 7936 KB
1_107.txt AC 37 ms 7552 KB
1_108.txt WA
1_109.txt AC 47 ms 7936 KB
1_110.txt AC 47 ms 7936 KB
1_111.txt AC 47 ms 7936 KB
1_112.txt AC 51 ms 7936 KB
1_113.txt AC 35 ms 7552 KB
1_114.txt WA
1_115.txt AC 47 ms 7936 KB
1_116.txt AC 46 ms 7936 KB