Submission #2504953


Source Code Expand

/**
 * File    : F.cpp
 * Author  : Kazune Takahashi
 * Created : 2018-5-12 22:17:51
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <chrono>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};

// const int C = 1e6+10;
// const ll M = 1000000007;

int N;
int x[100010];
int y[100010];
string S;
vector<int> T[100010];
vector<int> V[100010];
int root;
int parent[100010];
bool need[100010];
int maxi = 0;
std::chrono::system_clock::time_point start_time, end_time;

int dfs(int v)
{
  end_time = std::chrono::system_clock::now();
  double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time).count();
  if (elapsed > 1900)
  {
    assert(false);
  }
  int ans = (need[v] ? 1 : 0);
  vector<int> X;
  for (auto e : V[v])
  {
    if (e == parent[v])
    {
      continue;
    }
    else
    {
      parent[e] = v;
      X.push_back(dfs(e));
    }
  }
  if ((int)X.size() == 0)
  {
    return ans;
  }
  else if ((int)X.size() == 1)
  {
    ans += X[0];
    maxi = max(maxi, ans);
    return ans;
  }
  else
  {
    sort(X.begin(), X.end());
    reverse(X.begin(), X.end());
    ans += X[0] + X[1];
    maxi = max(maxi, ans);
    return ans - X[1];
  }
}

int main()
{
  start_time = std::chrono::system_clock::now();
  int N;
  cin >> N;
  for (auto i = 0; i < N - 1; i++)
  {
    cin >> x[i] >> y[i];
    x[i]--;
    y[i]--;
    T[x[i]].push_back(y[i]);
    T[y[i]].push_back(x[i]);
  }
  cin >> S;
  bool allb = true;
  for (auto i = 0; i < N; i++)
  {
    if (S[i] == 'W')
    {
      allb = false;
      break;
    }
  }
  if (allb)
  {
    cout << 0 << endl;
    return 0;
  }
  queue<int> st;
  for (auto i = 0; i < N; i++)
  {
    if ((int)T[i].size() == 1 && S[i] == 'B')
    {
      // cerr << i << " pushed." << endl;
      st.push(i);
    }
  }
  bool del[100010];
  fill(del, del + 100010, false);
  while (!st.empty())
  {
    int now = st.front();
    st.pop();
    int cnt = 0;
    if (del[now])
    {
      continue;
    }
    for (auto e : T[now])
    {
      if (!del[e])
      {
        cnt++;
      }
    }
    if (cnt <= 1)
    {
      del[now] = true;
      // cerr << "del[" << now << "]" << endl;
      for (auto f : T[now])
      {
        if (!del[f] && S[f] == 'B')
        {
          st.push(f);
        }
      }
    }
  }
  int M = 0;
  for (auto i = 0; i < N - 1; i++)
  {
    if (!del[x[i]] && !del[y[i]])
    {
      V[x[i]].push_back(y[i]);
      V[y[i]].push_back(x[i]);
      M++;
    }
  }
  M++;
  int cost = 0;
  fill(need, need + 100010, false);
  for (auto i = 0; i < N; i++)
  {
    if (del[i])
    {
      continue;
    }
    if ((((int)V[i].size()) % 2 == 0) ^ (S[i] == 'B'))
    {
      cost++;
      need[i] = true;
    }
  }
  // cerr << "cost = " << cost << endl;
  for (auto i = 0; i < N; i++)
  {
    if (!del[i] && S[i] == 'W')
    {
      root = i;
      break;
    }
  }
  parent[root] = -1;
  dfs(root);
  cout << 2 * (M - 1) + cost - maxi * 2 << endl;
}

Submission Info

Submission Time
Task F - Monochrome Cat
User kazunetakahashi
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3763 Byte
Status TLE
Exec Time 2115 ms
Memory 22016 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 4
AC × 117
TLE × 1
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 5120 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 4992 KB
1_018.txt AC 3 ms 5120 KB
1_019.txt AC 3 ms 5120 KB
1_020.txt AC 3 ms 4992 KB
1_021.txt AC 3 ms 5120 KB
1_022.txt AC 3 ms 5120 KB
1_023.txt AC 3 ms 4992 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 4992 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 4992 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 48 ms 10368 KB
1_046.txt AC 58 ms 12288 KB
1_047.txt AC 83 ms 8960 KB
1_048.txt AC 66 ms 8320 KB
1_049.txt AC 107 ms 17024 KB
1_050.txt AC 92 ms 14336 KB
1_051.txt AC 102 ms 12152 KB
1_052.txt AC 20 ms 6528 KB
1_053.txt AC 67 ms 8824 KB
1_054.txt AC 29 ms 6780 KB
1_055.txt AC 100 ms 12152 KB
1_056.txt AC 37 ms 7420 KB
1_057.txt AC 5 ms 5248 KB
1_058.txt AC 61 ms 10240 KB
1_059.txt AC 30 ms 6400 KB
1_060.txt AC 67 ms 8320 KB
1_061.txt AC 121 ms 14208 KB
1_062.txt AC 56 ms 9856 KB
1_063.txt AC 79 ms 10112 KB
1_064.txt AC 158 ms 8192 KB
1_065.txt AC 7 ms 5248 KB
1_066.txt AC 1291 ms 8700 KB
1_067.txt AC 24 ms 6656 KB
1_068.txt AC 333 ms 8192 KB
1_069.txt AC 35 ms 7168 KB
1_070.txt AC 57 ms 8320 KB
1_071.txt AC 67 ms 8448 KB
1_072.txt AC 44 ms 7296 KB
1_073.txt AC 14 ms 5888 KB
1_074.txt AC 9 ms 5504 KB
1_075.txt AC 57 ms 8448 KB
1_076.txt AC 125 ms 11776 KB
1_077.txt AC 65 ms 8320 KB
1_078.txt AC 26 ms 6400 KB
1_079.txt AC 57 ms 8320 KB
1_080.txt AC 53 ms 8064 KB
1_081.txt AC 142 ms 17664 KB
1_082.txt AC 146 ms 20864 KB
1_083.txt AC 81 ms 9088 KB
1_084.txt AC 85 ms 9216 KB
1_085.txt AC 146 ms 22016 KB
1_086.txt AC 146 ms 20992 KB
1_087.txt AC 124 ms 14200 KB
1_088.txt AC 104 ms 12152 KB
1_089.txt AC 78 ms 9464 KB
1_090.txt AC 81 ms 9976 KB
1_091.txt AC 134 ms 14200 KB
1_092.txt AC 77 ms 9464 KB
1_093.txt AC 159 ms 15616 KB
1_094.txt AC 140 ms 16896 KB
1_095.txt AC 87 ms 9216 KB
1_096.txt AC 89 ms 9344 KB
1_097.txt AC 155 ms 17280 KB
1_098.txt AC 133 ms 15744 KB
1_099.txt AC 146 ms 13436 KB
1_100.txt AC 130 ms 12028 KB
1_101.txt AC 85 ms 9212 KB
1_102.txt TLE 2115 ms 9596 KB
1_103.txt AC 150 ms 13436 KB
1_104.txt AC 110 ms 11132 KB
1_105.txt AC 159 ms 12800 KB
1_106.txt AC 134 ms 11904 KB
1_107.txt AC 88 ms 9088 KB
1_108.txt AC 94 ms 9344 KB
1_109.txt AC 164 ms 12800 KB
1_110.txt AC 137 ms 11392 KB
1_111.txt AC 158 ms 12800 KB
1_112.txt AC 136 ms 11904 KB
1_113.txt AC 87 ms 9088 KB
1_114.txt AC 87 ms 9344 KB
1_115.txt AC 156 ms 12800 KB
1_116.txt AC 132 ms 11392 KB