Submission #8381081


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

vector <int> e[200005];
int d[200005];

bool ban[200005],val[200005];

int dis[200005];

int dfs(int x,int fa) {
  dis[x]=dis[fa]+val[x];
  int ans=x;
  for(int i=0;i<e[x].size();i++)
    if (e[x][i]!=fa&&!ban[e[x][i]]) {
    	int u=e[x][i];
    	int t=dfs(u,x);
    	if (dis[t]>dis[ans]) ans=t;
	}
  return ans;
}

char str[200005];
queue <int> q;

int main() {
  int n;
  scanf("%d",&n);
  for(int i=1;i<n;i++) {
  	int x,y;
  	scanf("%d%d",&x,&y);
  	e[x].push_back(y);
  	e[y].push_back(x);
  	d[x]++;d[y]++;
  }
  scanf("%s",str+1);
  bool ok=0;
  for(int i=1;i<=n;i++) {
  	val[i]=(str[i]=='W');
  	ok|=val[i];
  }
  if (!ok) {
  	puts("0");
  	return 0;
  }
  for(int i=1;i<=n;i++)
    if (!val[i]&&d[i]<=1) q.push(i);
  while (!q.empty()) {
  	int x=q.front();q.pop();
  	ban[x]=1;
  	for(int i=0;i<e[x].size();i++)
  	  if (!ban[e[x][i]]) {
  	  	  int u=e[x][i];
  	  	  d[u]--;
  	  	  if (!val[u]&&d[u]<=1) q.push(u);
		}
  }
  int rt=0,s=-2;
  for(int i=1;i<=n;i++)
    if (!ban[i]) {
    	rt=i;
    	for(int j=0;j<e[i].size();j++)
    	  if (!ban[e[i][j]]) val[e[i][j]]^=1;
    	s+=2;
	}
  for(int i=1;i<=n;i++)
    if (!ban[i]) s+=val[i];
  rt=dfs(rt,0);
  int x=dfs(rt,0);
  printf("%d\n",max(1,s-2*dis[x]));
  return 0;
}

Submission Info

Submission Time
Task F - Monochrome Cat
User mayaohua
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1358 Byte
Status AC
Exec Time 53 ms
Memory 15360 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:29:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
./Main.cpp:32:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&x,&y);
                       ^
./Main.cpp:37:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",str+1);
                    ^

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 5120 KB
0_001.txt AC 3 ms 5120 KB
0_002.txt AC 3 ms 4992 KB
0_003.txt AC 3 ms 5120 KB
1_003.txt AC 3 ms 5120 KB
1_004.txt AC 3 ms 4992 KB
1_005.txt AC 3 ms 4992 KB
1_006.txt AC 3 ms 5120 KB
1_007.txt AC 3 ms 5120 KB
1_008.txt AC 3 ms 5120 KB
1_009.txt AC 3 ms 5120 KB
1_010.txt AC 3 ms 5120 KB
1_011.txt AC 3 ms 4992 KB
1_012.txt AC 3 ms 5120 KB
1_013.txt AC 3 ms 5120 KB
1_014.txt AC 3 ms 5120 KB
1_015.txt AC 3 ms 5120 KB
1_016.txt AC 3 ms 5120 KB
1_017.txt AC 3 ms 5120 KB
1_018.txt AC 3 ms 5120 KB
1_019.txt AC 3 ms 5120 KB
1_020.txt AC 3 ms 5120 KB
1_021.txt AC 3 ms 5120 KB
1_022.txt AC 3 ms 5120 KB
1_023.txt AC 3 ms 5120 KB
1_024.txt AC 3 ms 5120 KB
1_025.txt AC 3 ms 5120 KB
1_026.txt AC 3 ms 5120 KB
1_027.txt AC 3 ms 5120 KB
1_028.txt AC 3 ms 5120 KB
1_029.txt AC 3 ms 5120 KB
1_030.txt AC 3 ms 5120 KB
1_031.txt AC 3 ms 5120 KB
1_032.txt AC 3 ms 5120 KB
1_033.txt AC 3 ms 5120 KB
1_034.txt AC 3 ms 5120 KB
1_035.txt AC 3 ms 5120 KB
1_036.txt AC 3 ms 5120 KB
1_037.txt AC 3 ms 5120 KB
1_038.txt AC 3 ms 5120 KB
1_039.txt AC 3 ms 5120 KB
1_040.txt AC 3 ms 5120 KB
1_041.txt AC 3 ms 4992 KB
1_042.txt AC 3 ms 5120 KB
1_043.txt AC 3 ms 5120 KB
1_044.txt AC 3 ms 5120 KB
1_045.txt AC 18 ms 8704 KB
1_046.txt AC 22 ms 9600 KB
1_047.txt AC 34 ms 8704 KB
1_048.txt AC 29 ms 7936 KB
1_049.txt AC 34 ms 10752 KB
1_050.txt AC 31 ms 11648 KB
1_051.txt AC 25 ms 8440 KB
1_052.txt AC 8 ms 6016 KB
1_053.txt AC 24 ms 8568 KB
1_054.txt AC 12 ms 6652 KB
1_055.txt AC 24 ms 8440 KB
1_056.txt AC 15 ms 7164 KB
1_057.txt AC 3 ms 5120 KB
1_058.txt AC 23 ms 8448 KB
1_059.txt AC 13 ms 6400 KB
1_060.txt AC 30 ms 8064 KB
1_061.txt AC 40 ms 10880 KB
1_062.txt AC 22 ms 8448 KB
1_063.txt AC 24 ms 7680 KB
1_064.txt AC 20 ms 7040 KB
1_065.txt AC 4 ms 5248 KB
1_066.txt AC 29 ms 8444 KB
1_067.txt AC 9 ms 5888 KB
1_068.txt AC 21 ms 7424 KB
1_069.txt AC 13 ms 6144 KB
1_070.txt AC 23 ms 7040 KB
1_071.txt AC 29 ms 8192 KB
1_072.txt AC 21 ms 7168 KB
1_073.txt AC 6 ms 5376 KB
1_074.txt AC 5 ms 5376 KB
1_075.txt AC 20 ms 6784 KB
1_076.txt AC 45 ms 9344 KB
1_077.txt AC 29 ms 8064 KB
1_078.txt AC 13 ms 6272 KB
1_079.txt AC 20 ms 6784 KB
1_080.txt AC 22 ms 7168 KB
1_081.txt AC 50 ms 15360 KB
1_082.txt AC 52 ms 15360 KB
1_083.txt AC 35 ms 8704 KB
1_084.txt AC 39 ms 8832 KB
1_085.txt AC 49 ms 12928 KB
1_086.txt AC 53 ms 15360 KB
1_087.txt AC 33 ms 9592 KB
1_088.txt AC 34 ms 9848 KB
1_089.txt AC 29 ms 9208 KB
1_090.txt AC 30 ms 9720 KB
1_091.txt AC 33 ms 9592 KB
1_092.txt AC 28 ms 9208 KB
1_093.txt AC 48 ms 12288 KB
1_094.txt AC 49 ms 12416 KB
1_095.txt AC 34 ms 8832 KB
1_096.txt AC 40 ms 8960 KB
1_097.txt AC 48 ms 10880 KB
1_098.txt AC 50 ms 12544 KB
1_099.txt AC 40 ms 9340 KB
1_100.txt AC 42 ms 9596 KB
1_101.txt AC 32 ms 8956 KB
1_102.txt AC 36 ms 9340 KB
1_103.txt AC 40 ms 9340 KB
1_104.txt AC 40 ms 9724 KB
1_105.txt AC 46 ms 9216 KB
1_106.txt AC 47 ms 9344 KB
1_107.txt AC 35 ms 8832 KB
1_108.txt AC 40 ms 9088 KB
1_109.txt AC 46 ms 9216 KB
1_110.txt AC 47 ms 9472 KB
1_111.txt AC 46 ms 9216 KB
1_112.txt AC 47 ms 9472 KB
1_113.txt AC 35 ms 8832 KB
1_114.txt AC 40 ms 9088 KB
1_115.txt AC 46 ms 9216 KB
1_116.txt AC 46 ms 9472 KB