Submission #2500901


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#ifdef MAROON_LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

ll read(){
	ll i;
	scanf("%" SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

const int Nmax=100010;
int k[Nmax];
bool inc[Nmax];
vi tr[Nmax];
int dfs1(int v,int p){
	int res=k[v];
	for(auto ch:tr[v])if(ch!=p)
		res+=dfs1(ch,v);
	inc[v]=res;
	return res;
}

int ans;
pi dfs2(int v,int p){
	vi ups{0},dws{0};
	for(auto ch:tr[v])if(ch!=p){
		pi g=dfs2(ch,v);
		ups.PB(g.first+(k[v]?2:0));
		dws.PB(g.second+(k[ch]?2:0));
	}
	int um=0,dm=0,s=ups.size();
	REP(i,s){
		chmax(ans,um+dws[i]);
		chmax(ans,dm+ups[i]);
		chmax(um,ups[i]);
		chmax(dm,dws[i]);
	}
	return pi(*max_element(ALL(ups)),*max_element(ALL(dws)));
}

signed main(){
	int n=read();
	REP(_,n-1){
		int x=read()-1,y=read()-1;
		tr[x].PB(y);
		tr[y].PB(x);
	}
	{
		string c=readString();
		if(c==string(n,'B')){
			print(0);
			return 0;
		}
		REP(i,n)
			k[i]=c[i]=='W';
	}
	int root=-1;
	REP(i,n)if(k[i])
		root=i;
	dfs1(root,-1);
	
	int base=0;
	int cnt=0;
	REP(i,n)if(inc[i]){
		cnt++;
		vi tmp;
		for(auto to:tr[i])if(inc[to]){
			k[i]^=1;
			tmp.PB(to);
		}
		tr[i]=tmp;
		base+=k[i];
	}
	cerr<<cnt<<endl;
	
	base+=(cnt-1)*2;
	cerr<<base<<endl;
	
	dfs2(root,-1);
	
	print(base-ans);
}

Submission Info

Submission Time
Task F - Monochrome Cat
User maroonrk
Language C++14 (GCC 5.4.1)
Score 800
Code Size 3445 Byte
Status AC
Exec Time 96 ms
Memory 31416 KB

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:55:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%" SCNd64,&i);
                      ^
./Main.cpp: In function ‘std::string readString()’:
./Main.cpp:77:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",buf);
                 ^
./Main.cpp: In function ‘char* readCharArray()’:
./Main.cpp:85:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",ret);
                 ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 4
AC × 118
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 3 ms 6400 KB
0_001.txt AC 3 ms 6400 KB
0_002.txt AC 3 ms 6400 KB
0_003.txt AC 3 ms 6400 KB
1_003.txt AC 3 ms 6400 KB
1_004.txt AC 3 ms 6400 KB
1_005.txt AC 3 ms 6400 KB
1_006.txt AC 3 ms 6400 KB
1_007.txt AC 3 ms 6400 KB
1_008.txt AC 3 ms 6400 KB
1_009.txt AC 3 ms 6400 KB
1_010.txt AC 3 ms 6400 KB
1_011.txt AC 3 ms 6400 KB
1_012.txt AC 3 ms 6400 KB
1_013.txt AC 3 ms 6400 KB
1_014.txt AC 3 ms 6400 KB
1_015.txt AC 3 ms 6400 KB
1_016.txt AC 3 ms 6400 KB
1_017.txt AC 3 ms 6400 KB
1_018.txt AC 3 ms 6400 KB
1_019.txt AC 3 ms 6400 KB
1_020.txt AC 3 ms 6400 KB
1_021.txt AC 3 ms 6400 KB
1_022.txt AC 3 ms 6400 KB
1_023.txt AC 3 ms 6400 KB
1_024.txt AC 3 ms 6400 KB
1_025.txt AC 3 ms 6400 KB
1_026.txt AC 3 ms 6400 KB
1_027.txt AC 3 ms 6400 KB
1_028.txt AC 3 ms 6400 KB
1_029.txt AC 3 ms 6400 KB
1_030.txt AC 3 ms 6400 KB
1_031.txt AC 3 ms 6400 KB
1_032.txt AC 3 ms 6400 KB
1_033.txt AC 3 ms 6400 KB
1_034.txt AC 3 ms 6400 KB
1_035.txt AC 3 ms 6400 KB
1_036.txt AC 3 ms 6400 KB
1_037.txt AC 3 ms 6400 KB
1_038.txt AC 3 ms 6400 KB
1_039.txt AC 3 ms 6400 KB
1_040.txt AC 3 ms 6400 KB
1_041.txt AC 3 ms 6400 KB
1_042.txt AC 3 ms 6400 KB
1_043.txt AC 3 ms 6400 KB
1_044.txt AC 3 ms 6400 KB
1_045.txt AC 28 ms 11392 KB
1_046.txt AC 33 ms 13184 KB
1_047.txt AC 35 ms 9600 KB
1_048.txt AC 33 ms 11368 KB
1_049.txt AC 58 ms 24048 KB
1_050.txt AC 49 ms 17664 KB
1_051.txt AC 36 ms 11940 KB
1_052.txt AC 9 ms 7420 KB
1_053.txt AC 25 ms 9844 KB
1_054.txt AC 12 ms 7800 KB
1_055.txt AC 35 ms 11820 KB
1_056.txt AC 16 ms 8312 KB
1_057.txt AC 4 ms 6528 KB
1_058.txt AC 33 ms 12800 KB
1_059.txt AC 15 ms 7680 KB
1_060.txt AC 33 ms 10472 KB
1_061.txt AC 64 ms 18008 KB
1_062.txt AC 31 ms 12288 KB
1_063.txt AC 37 ms 9360 KB
1_064.txt AC 23 ms 8316 KB
1_065.txt AC 5 ms 6656 KB
1_066.txt AC 30 ms 9464 KB
1_067.txt AC 13 ms 7364 KB
1_068.txt AC 24 ms 8616 KB
1_069.txt AC 19 ms 7424 KB
1_070.txt AC 30 ms 8192 KB
1_071.txt AC 32 ms 9600 KB
1_072.txt AC 22 ms 8320 KB
1_073.txt AC 8 ms 6784 KB
1_074.txt AC 5 ms 6656 KB
1_075.txt AC 31 ms 8064 KB
1_076.txt AC 67 ms 10112 KB
1_077.txt AC 31 ms 9472 KB
1_078.txt AC 14 ms 7552 KB
1_079.txt AC 31 ms 8064 KB
1_080.txt AC 29 ms 8192 KB
1_081.txt AC 79 ms 21176 KB
1_082.txt AC 80 ms 24888 KB
1_083.txt AC 36 ms 9728 KB
1_084.txt AC 43 ms 13496 KB
1_085.txt AC 86 ms 31416 KB
1_086.txt AC 96 ms 30136 KB
1_087.txt AC 46 ms 13156 KB
1_088.txt AC 39 ms 11500 KB
1_089.txt AC 30 ms 10484 KB
1_090.txt AC 31 ms 10484 KB
1_091.txt AC 46 ms 13156 KB
1_092.txt AC 31 ms 10484 KB
1_093.txt AC 76 ms 16056 KB
1_094.txt AC 71 ms 16952 KB
1_095.txt AC 38 ms 10240 KB
1_096.txt AC 43 ms 11448 KB
1_097.txt AC 76 ms 16184 KB
1_098.txt AC 66 ms 16184 KB
1_099.txt AC 60 ms 11248 KB
1_100.txt AC 52 ms 10872 KB
1_101.txt AC 34 ms 10232 KB
1_102.txt AC 37 ms 10232 KB
1_103.txt AC 61 ms 11248 KB
1_104.txt AC 47 ms 10712 KB
1_105.txt AC 72 ms 10240 KB
1_106.txt AC 65 ms 10240 KB
1_107.txt AC 37 ms 10240 KB
1_108.txt AC 42 ms 10240 KB
1_109.txt AC 72 ms 10240 KB
1_110.txt AC 60 ms 10240 KB
1_111.txt AC 72 ms 10240 KB
1_112.txt AC 65 ms 10240 KB
1_113.txt AC 38 ms 10240 KB
1_114.txt AC 42 ms 10240 KB
1_115.txt AC 71 ms 10240 KB
1_116.txt AC 60 ms 10240 KB