제출 #107867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107867		shoemakerjo	Mergers (JOI19_mergers)	C++14	100 / 100	2065 ms	172724 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500010;
int n, k;

int cset[maxn]; //store for the states
int mstate[maxn]; //store for the nodes
int croot[maxn];

#define pii pair<int, int>

vector<int> adj[maxn];

int findset(int u) {
  if (cset[u] == u) return u;
  return cset[u] = findset(cset[u]);
}

void unionset(int a, int b) {
  a = findset(a);
  b = findset(b);
  if (a == b) return;
  if (rand()%2) cset[a] = b;
  else cset[b] = a;
}

int getcomp(int u) {
  return findset(mstate[u]);
}

int par[20][maxn];
int dep[maxn];
int subsize[maxn];

int walk(int u, int k) {
  for (int i = 0; i < 19; i++) {
    if (k & (1 << i)) {
      u = par[i][u];
    }
  }
  return u;
}

int lca(int a, int b) {
  // cout << a << " and " << b << endl;
  if (dep[a] < dep[b]) swap(a, b);
  a = walk(a, dep[a] - dep[b]);
  if (a == b) return a;
  for (int i = 19; i >= 0; i--) {
    if (par[i][a] != par[i][b]) {
      a = par[i][a];
      b = par[i][b];
    }
  }
  return par[0][a];
}

void predfs(int u, int p = -1) {
  dep[u] = p == -1 ? 1 : dep[p]+1;
  subsize[u] = 1;
  par[0][u] = p == -1 ? 0 : p;
  for (int v : adj[u]) {
    if (v == p) continue;
    predfs(v, u);
    subsize[u] += subsize[v];
  }
}

// set<pii> curin;
vector<int> myremos[maxn];

void dfs(int u, int p, set<pii>& curin) {

  // cout << " doing " << u << endl;

  int bigch = -1;
  for (int v : adj[u]) {
    if (v == p) continue;
    if (bigch == -1 || subsize[v] > subsize[bigch]) {
      bigch = v;
    }
  }
  if (bigch != -1) {
    dfs(bigch, u, curin);
  }

  for (int v : adj[u]) {
    if (v == p || v == bigch) continue;
    set<pii> tc;
    dfs(v, u, tc);
    for (pii vp : tc) curin.insert(vp);
  }



  if (curin.size()) {
    int cv = (*(curin.begin())).second;
    unionset(cv, mstate[u]);
  }
  curin.insert(pii(dep[croot[mstate[u]]], mstate[u]));

  // cout << u << " : ";
  // for (pii vp : curin) {
  //   cout << vp.first << "," << vp.second << " ";
  // }
  // cout << endl;

  int cv = (*(curin.begin())).second;

  for (int v : myremos[u]) {
    unionset(cv, v);
    curin.erase(curin.find(pii(dep[u], v)));
  }
}

int deg[maxn];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> k;
  int u, v;
  for (int i = 0; i < n-1; i++) {
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 1; i <= k; i++) {
    cset[i] = i;
  }
  for (int i = 1; i <= n; i++) {
    cin >> mstate[i];
  }
  predfs(1);
  for (int i = 1; i < 20; i++) {
    for (int j = 1; j <= n; j++) {
      if (par[i-1][j] != 0) {
        par[i][j] = par[i-1][par[i-1][j]];
      }
      else par[i][j] = 0;
    }
  }
  //now we are ready to union components
  for (int i= 1; i <= n; i++) {
    if (croot[mstate[i]] == 0) {
      croot[mstate[i]] = i;
    }
    else {
      croot[mstate[i]] = lca(croot[mstate[i]], i);
    }
  }
  for (int i = 1; i <= k; i++) {
    myremos[croot[i]].push_back(i);
    // cout << i << " :: " << croot[i] << endl;
  }
  for (int i = 1; i <= n; i++) {
    reverse(myremos[i].begin(), myremos[i].end());
  }

  set<pii> tc;
  dfs(1, -1, tc);

  for (int i = 1; i <= n; i++) {
    for (int j : adj[i]) {
      if (getcomp(i) != getcomp(j)) {
        deg[getcomp(i)]++;
        deg[getcomp(j)]++;
      }
    }
  }
  int nc = 0;
  for (int i = 1; i <= k; i++) {
    assert(deg[i]%2 == 0);
    deg[i] /= 2;
    if (deg[i] == 1) nc++;
  }

  // cout << "sz: " << curin.size() << endl;

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

}

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