제출 #128319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128319		Mohammad_Yasser	Mergers (JOI19_mergers)	C++14	0 / 100	3021 ms	18544 KiB

mergers

#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 deg[N];

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) {
    for (int v : adj[i]) {
      if (color[v] != color[i]) {
        ++deg[color[v]];
        ++deg[color[i]];
      }
    }
  }

  for (int i = 1; i <= n; ++i) {
    res += (deg[i] == 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;

}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30