Submission #630936

#	Time	Username	Problem	Language	Result	Execution time	Memory
630936		cadmiumsky	Mergers (JOI19_mergers)	C++14	0 / 100	124 ms	26084 KiB

mergers

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5, nbit = 18;

int n, k;
vector<int> g[nmax];

#define lsb(x) (x & -x)
namespace AIB {
  int tree[nmax], len;
  void init(int nlen) {
    len = nlen;
  }
  void upd(int x, int val) {
    while(x > 0) tree[x] += val, x -= lsb(x);
  }
  int query(int x) {
    int sum = 0;
    while(x <= n) sum += tree[x], x += lsb(x);
    return sum;
  }
  int query(int l, int r) {
    return query(r) - query(l - 1);
  }
}

int pin[nmax], pout[nmax], inp = 1;
namespace LCA {
  int p[nmax][nbit];
  void init(int node, int f) {
    pin[node] = inp++;
    p[node][0] = f;
    for(int i = 1; i < nbit; i++)
      p[node][i] = p[p[node][i - 1]][i - 1];
    for(auto x : g[node])
      if(x == f) continue;
      else init(x, node);
    pout[node] = inp++;
  }
  bool isanc(int x, int y) {return pin[x] <= pin[y] && pout[y] <= pout[x]; }
  int lca(int x, int y) {
    if(isanc(x, y)) return x;
    if(isanc(y, x)) return y;
    for(int i = nbit - 1; i >= 0; i--)
      if(!isanc(p[x][i], y))	
	x = p[x][i];
    return p[x][0];
  }
};

vector<int> ofcol[nmax];
int lca[nmax];
int start[nmax], fin[nmax];
int cnt;

vector<int> cuts;
int identify(int node, int f) {
  int sum = start[node] + fin[node];
  for(auto x : g[node]) {
    if(x == f) continue;
    int tmp = identify(x, node);
    if(tmp == 0)
      cuts.push_back(x);
    else
      sum += tmp;
  }
  return sum;
}

int noise_reduction(int node, int f) {
  int sum = 0;
  for(auto x : g[node]) {
    if(x == f) continue;
    sum += noise_reduction(x, node);
  }
  if(sum == 0 && start[node] == 1)
    cnt++;
  return sum + start[node];
}

signed main() {
  cin >> n >> k;
  for(int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  LCA::init(1, 1);
  AIB::init(inp);
  for(int i = 1, x; i <= n; i++) {
    cin >> x;
    ofcol[x].push_back(i); 
  }
  for(int i = 1; i <= k; i++) {
    lca[i] = ofcol[i].back();
    for(auto x : ofcol[i])
      lca[i] = LCA::lca(x, lca[i]);
    for(auto x : ofcol[i])
      start[x]++, 
      fin[lca[i]]--;
  }
  //for(int i = 1; i <= n; i++)
    //cerr << pin[i] << ' ' << pout[i] << '\n';
  identify(1, 1);
  for(int i = 1; i <= n; i++)
    start[i] = 0;
  for(auto x : cuts)
    start[x] = 1;
   noise_reduction(1, 1);
   
  cout << (cnt + 1) / 2 << '\n';
}

/**
  De-atâtea nopți aud plouând,
  Aud materia plângând..
  Sînt singur, și mă duce un gând
  Spre locuințele lacustre.

  Și parcă dorm pe scânduri ude,
  În spate mă izbește-un val --
  Tresar prin somn și mi se pare
  Că n-am tras podul de la mal.

  Un gol istoric se întinde,
  Pe-același vremuri mă găsesc..
  Și simt cum de atâta ploaie
  Pilonii grei se prăbușesc.

  De-atâtea nopți aud plouând,
  Tot tresărind, tot așteptând..
  Sînt singur, și mă duce-un gând
  Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/

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