oj.uz

Submission #128240

# Submission time Handle Problem Language Result Execution time Memory
128240 2019-07-10T14:59:12 Z Mohammad_Yasser Mergers (JOI19_mergers) C++14
0 / 100
 3000 ms 18092 KB 
#ifndef Local
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define popCnt(x) (__builtin_popcountll(x))
typedef long long Long;

const int N = 5e5 + 5;

vector<int> adj[N];
int color[N];

struct DSU {
  int parent[N];

  void init() {
    for (int i = 0; i < N; ++i) {
      parent[i] = i;
    }
  }

  int getRoot(int x) {
    if (parent[x] == x) return x;
    return parent[x] = getRoot(parent[x]);
  }

  bool join(int x, int y) {
    x = getRoot(x), y = getRoot(y);
    if (x == y) return false;
    parent[x] = y;
    return true;
  }

} dsu;

bool solve(int node, int parent, int clr) {
  bool res = (color[node] == clr);

  for (auto& child : adj[node]) {
    if (child == parent) continue;
    res |= solve(child, node, clr);
  }

  if (res) {
    dsu.join(color[node], clr);
  }

  return res;
}

int n, k;

int countLeaves() {
  int res = 0;

  for (int i = 1; i <= n; ++i) {
    color[i] = dsu.getRoot(color[i]);
  }

  for (int i = 1; i <= n; ++i) {
    int d = 0;
    for (int v : adj[i]) {
      d += (color[v] != color[i]);
    }
    res += (d == 1);
  }

  for (int i = 1; i <= n; ++i) {
    for (int v1 : adj[i]) {
      for (int v2 : adj[i]) {
        if (color[v1] == color[i] || color[v2] == color[i]) continue;
        assert(v1 == v2 || color[v1] != color[v2]);
      }
    }
  }

  assert(res != 1);
  return res;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
#ifdef Local
  freopen("test.in", "r", stdin);
#else
#define endl '\n'
#endif

  cin >> n >> k;

  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  for (int i = 1; i <= n; ++i) {
    cin >> color[i];
  }

  dsu.init();

  for (int i = 1; i <= n; ++i) {
    solve(i, -1, color[i]);
  }

  cout << (countLeaves() + 1) / 2 << endl;

}

Compilation message

mergers.cpp:5:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:1024000000,1024000000")

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14200 KB Output is correct
2 Correct 16 ms 14072 KB Output is correct
3 Incorrect 16 ms 14072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14200 KB Output is correct
2 Correct 16 ms 14072 KB Output is correct
3 Incorrect 16 ms 14072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14200 KB Output is correct
2 Correct 16 ms 14072 KB Output is correct
3 Incorrect 16 ms 14072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3032 ms 18092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14200 KB Output is correct
2 Correct 16 ms 14072 KB Output is correct
3 Incorrect 16 ms 14072 KB Output isn't correct
4 Halted 0 ms 0 KB -