oj.uz

Submission #630940

# Submission time Handle Problem Language Result Execution time Memory
630940 2022-08-17T11:06:44 Z cadmiumsky Mergers (JOI19_mergers) C++14
0 / 100
 100 ms 21916 KB 
#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) || (sum == 1 && node == f))
    cnt++;
  return start[node]? start[node] : sum;
}

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);
  cuts.push_back(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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 8 ms 9664 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Incorrect 5 ms 9684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 8 ms 9664 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Incorrect 5 ms 9684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 8 ms 9664 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Incorrect 5 ms 9684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 8 ms 9664 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Incorrect 5 ms 9684 KB Output isn't correct
6 Halted 0 ms 0 KB -