oj.uz

Submission #128196

# Submission time Handle Problem Language Result Execution time Memory
128196 2019-07-10T13:53:13 Z Mohammad_Yasser Mergers (JOI19_mergers) C++14
0 / 100
 86 ms 20472 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;

int color_cnt[N];
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;
    color_cnt[y] += color_cnt[x];
    return true;
  }

} dsu;

int node_cnt[N];

void solve(int node, int parent) {
  for (auto& child : adj[node]) {
    if (child == parent) continue;
    solve(child, node);
    if (node_cnt[child] == color_cnt[color[child]]) {
      continue;
    }
    dsu.join(color[node], color[child]);
    node_cnt[node] += node_cnt[child];
  }

  ++node_cnt[node];
  color[node] = dsu.getRoot(color[node]);

//  cout << node << " " << color[node] << " " << node_cnt[node] << " "
//    << color_cnt[color[node]] << endl;
}
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]);
    }
//    cout << i << " " << color[i] << " " << d << endl;
    res += (d == 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];
    ++color_cnt[color[i]];
  }

  dsu.init();

  solve(1, -1);

  cout << max(countLeaves() - 1, 0) << 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 Incorrect 15 ms 14072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 14072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 14072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 19824 KB Output is correct
2 Incorrect 86 ms 20472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 14072 KB Output isn't correct
2 Halted 0 ms 0 KB -