답안 #1042962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042962 2024-08-03T15:48:43 Z juicy Unique Cities (JOI19_ho_t5) C++17
32 / 100
494 ms 42836 KB
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, m;
int c[N], dep[N], res[N], sf[N], mx[N], l[N], lst[N], s[4 * N], lz[4 * N], cnt[4 * N];
vector<int> g[N];

void pul(int id) {
  s[id] = min(s[id * 2], s[id * 2 + 1]);
  cnt[id] = 0;
  for (auto i : {id * 2, id * 2 + 1}) {
    if (s[id] == s[i]) {
      cnt[id] += cnt[i];
    }
  }
}

void bld(int id = 1, int l = 1, int r = n) {
  lz[id] = 0;
  if (l == r) {
    s[id] = 1;
    cnt[id] = 1;
    return;
  }
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r);
  pul(id); 
}

void app(int id, int x) {
  s[id] += x;
  lz[id] += x;
}

void psh(int id) {
  if (lz[id]) {
    app(id * 2, lz[id]);
    app(id * 2 + 1, lz[id]);
    lz[id] = 0;
  }
}

void upd(int u, int v, int x, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    app(id, x);
    return;
  }
  psh(id);
  int md = (l + r) / 2;
  if (u <= md) {
    upd(u, v, x, id * 2, l, md);
  }
  if (md < v) {
    upd(u, v, x, id * 2 + 1, md + 1, r);
  }
  pul(id);
}

int qry(int i, int id = 1, int l = 1, int r = n) {
  if (l == r) {
    return s[id];
  }
  psh(id);
  int md = (l + r) / 2;
  return i <= md ? qry(i, id * 2, l, md) : qry(i, id * 2 + 1, md + 1, r);
}

void dfs(int u, int p) {
  mx[u] = u;
  for (int v : g[u]) {
    if (v != p) {
      dep[v] = dep[u] + 1;
      dfs(v, u);
      if (dep[mx[v]] > dep[mx[u]]) {
        mx[u] = mx[v];
      }
    }
  }
}

void DFS(int u, int p) {
  int prv = -1;
  if (u ^ p) {
    if (!lst[c[p]] || qry(dep[lst[c[p]]])) {
      prv = lst[c[p]];
      lst[c[p]] = p;
      upd(dep[p], dep[p], -1);
    }
  }
  if (l[u] && dep[u] > 2) {
    upd(max(1, dep[u] - l[u]), dep[u] - 2, 1);
  }
  int h = dep[mx[u]] - dep[u];
  upd(max(1, dep[u] - h), dep[u], 1); 
  if (s[1] == 0) {
    res[u] = max(res[u], cnt[1]);
  }
  upd(max(1, dep[u] - h), dep[u], -1);
  {
    int k = g[u].size();
    sf[k] = 0;
    for (int i = k - 1; i >= 0; --i) {
      sf[i] = sf[i + 1];
      int v = g[u][i];
      if (v != p) {
        sf[i] = max(sf[i], dep[mx[v]] - dep[u] + 1);
      }
    }
    int pf = 0;
    for (int i = 0; i < k; ++i) {
      int v = g[u][i];
      if (v != p) {
        l[v] = max(pf, sf[i + 1]);
        pf = max(pf, dep[mx[v]] - dep[u] + 1);
      }
    }
    for (int v : g[u]) {
      if (v != p) {
        DFS(v, u);
      }
    }
  }
  if (~prv) {
    lst[c[p]] = prv;
    upd(dep[p], dep[p], 1);
  }
  if (l[u] && dep[u] > 2) {
    upd(max(1, dep[u] - l[u]), dep[u] - 2, -1);
  }
  l[u] = 0;
}

void solve(int u) {
  dep[u] = 1;
  dfs(u, u);
  bld();
  DFS(u, u);
}

int findbest(int r) {
  dep[r] = 0;
  dfs(r, r);
  return mx[r];
}

array<int, 2> diam() {
  int u = findbest(1);
  return {u, findbest(u)};
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }  
  for (int i = 1; i <= n; ++i) {
    cin >> c[i];
  }
  auto [a, b] = diam();
  solve(a);
  solve(b);
  for (int i = 1; i <= n; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Incorrect 4 ms 5176 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 174 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 311 ms 23256 KB Output is correct
2 Correct 410 ms 41552 KB Output is correct
3 Correct 54 ms 9552 KB Output is correct
4 Correct 383 ms 26448 KB Output is correct
5 Correct 439 ms 42836 KB Output is correct
6 Correct 426 ms 34388 KB Output is correct
7 Correct 365 ms 26708 KB Output is correct
8 Correct 440 ms 29972 KB Output is correct
9 Correct 418 ms 28820 KB Output is correct
10 Correct 407 ms 27728 KB Output is correct
11 Correct 329 ms 27208 KB Output is correct
12 Correct 494 ms 39756 KB Output is correct
13 Correct 416 ms 33724 KB Output is correct
14 Correct 455 ms 33748 KB Output is correct
15 Correct 367 ms 27224 KB Output is correct
16 Correct 431 ms 37832 KB Output is correct
17 Correct 431 ms 34772 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Incorrect 4 ms 5176 KB Output isn't correct
3 Halted 0 ms 0 KB -