oj.uz

Submission #863485

# Submission time Handle Problem Language Result Execution time Memory
863485 2023-10-20T12:37:04 Z NeroZein Mergers (JOI19_mergers) C++17
0 / 100
 45 ms 59076 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 5e5 + 5; 

int sz[N]; 
int od, id;
int leaves;
int col[N];
bool bad[N]; 
int in[N], out[N]; 
vector<int> vec[N]; 
vector<int> g[N];

int pre(int v, int p) {
  sz[v] = 1;
  for (int u : g[v]) {
    if (u != p) {
      pre(u, v); 
      sz[v] += sz[u];
    }
  }
  return sz[v];
}

void dfs(int v, int p, bool keep) {
  int big = 0;
  for (int u : g[v]) {
    if (u != p && sz[u] > sz[big]) {
      big = u; 
    }
  }
  for (int u : g[v]) {
    if (u != p && u != big) {
      dfs(u, v, false); 
    }
  }
  if (big) {
    dfs(big, v, true); 
    swap(vec[v], vec[big]); 
  }
  if (--out[col[v]] == 0) {
    od++; 
  }
  if (in[col[v]]++ == 0) {
    id++;
  }
  vec[v].push_back(v); 
  for (int u : g[v]) {
    if (u == p || u == big) {
      continue;
    }
    for (int x : vec[u]) {
      if (--out[col[x]] == 0) {
        od++;
      }
      if (in[col[x]]++ == 0) {
        id++; 
      }
      vec[v].push_back(u); 
    }
  }
  if (od == id) {
    bad[v] = true; 
  }
  if (!keep) {
    for (int u : vec[v]) {
      if (out[col[u]]++ == 0) {
        od--;
      }
      if (--in[col[u]] == 0) {
        id--;
      }
    }
    assert(od == 0 && id == 0);
  }
}

bool dfs2(int v, int p) {
  bool ret = false;
  for (int u : g[v]) {
    if (u != p) {
      ret |= dfs2(u, v); 
    }
  }
  if (!ret && bad[v]) {
    ret = true;
    leaves++; 
  }
  return ret;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> col[i]; 
    out[col[i]]++;
  }
  pre(1, 1); 
  dfs(1, 1, 1); 
  bad[1] = false;
  dfs2(1, 1); 
  cout << (leaves + 1) / 2 << '\n'; 
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB Output is correct
2 Runtime error 27 ms 59076 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB Output is correct
2 Runtime error 27 ms 59076 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB Output is correct
2 Runtime error 27 ms 59076 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 36820 KB Output is correct
2 Incorrect 43 ms 36992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB Output is correct
2 Runtime error 27 ms 59076 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -