oj.uz

Submission #1059144

# Submission time Handle Problem Language Result Execution time Memory
1059144 2024-08-14T17:46:50 Z MilosMilutinovic Unique Cities (JOI19_ho_t5) C++14
4 / 100
 2000 ms 37640 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    --c[i];
  }
  auto Bfs = [&](int v) {
    vector<int> d(n, -1);
    vector<int> que(1, v);
    d[v] = 0;
    for (int b = 0; b < (int) que.size(); b++) {
      int i = que[b];
      for (int j : g[i]) {
        if (d[j] == -1) {
          d[j] = d[i] + 1;
          que.push_back(j);
        }
      }
    }
    return d;
  }; 
  int x, y;
  {
    vector<int> d = Bfs(0);
    x = 0;
    for (int i = 1; i < n; i++) {
      if (d[i] > d[x]) {
        x = i;
      }
    }
  }
  {
    vector<int> d = Bfs(x);
    y = 0;
    for (int i = 1; i < n; i++) {
      if (d[i] > d[y]) {
        y = i;
      }
    }
  }
  vector<vector<int>> d(2);
  d[0] = Bfs(x);
  d[1] = Bfs(y);
  vector<int> res(n);
  for (int foo = 0; foo < 2; foo++) {
    int root = (foo == 0 ? x : y);
    vector<int> mx(n);
    vector<int> pr(n);
    function<void(int, int)> Dfs = [&](int v, int pv) {
      pr[v] = pv;
      mx[v] = 1;
      for (int u : g[v]) {
        if (u == pv) {
          continue;
        }
        Dfs(u, v);
        mx[v] = max(mx[v], mx[u] + 1);
      }
    };
    Dfs(root, root);
    vector<int> f(n, 1);
    auto Add = [&](int v, int d, int p) {
      while (d--) {
        f[v] += p;
        v = pr[v];
      }
    };
    function<void(int, int)> Solve = [&](int v, int pv) {
      if (d[foo][v] >= d[foo ^ 1][v]) {
        Add(v, mx[v], -1);
        vector<bool> was(m);
        res[v] = 0;
        for (int u = v; ; u = pr[u]) {
          if (f[u] == 1) {
            res[v] += !was[c[u]];
            was[c[u]] = true;
          }
          if (u == root) {
            break;
          }
        }
        Add(v, mx[v], +1);
      }
      multiset<int> st;
      for (int u : g[v]) {
        if (u == pv) {
          continue;
        }
        st.insert(mx[u]);
      }
      for (int u : g[v]) {
        if (u == pv) {
          continue;
        }
        st.erase(st.find(mx[u]));
        if (!st.empty()) {
          Add(pr[v], *prev(st.end()), -1);
        }
        Solve(u, v);
        if (!st.empty()) {
          Add(pr[v], *prev(st.end()), +1);
        }
        st.insert(mx[u]);
      }
    };
    Solve(root, root);
  }
  for (int i = 0; i < n; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 6 ms 588 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 12 ms 844 KB Output is correct
7 Correct 7 ms 604 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 12 ms 860 KB Output is correct
14 Correct 6 ms 604 KB Output is correct
15 Correct 6 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 11 ms 912 KB Output is correct
18 Correct 9 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 12 ms 896 KB Output is correct
21 Correct 7 ms 756 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 2 ms 688 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 12 ms 804 KB Output is correct
28 Correct 10 ms 860 KB Output is correct
29 Correct 7 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 11 ms 912 KB Output is correct
32 Correct 8 ms 604 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 11672 KB Output is correct
2 Execution timed out 2100 ms 22144 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 16668 KB Output is correct
2 Execution timed out 2070 ms 37640 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 6 ms 588 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 12 ms 844 KB Output is correct
7 Correct 7 ms 604 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 12 ms 860 KB Output is correct
14 Correct 6 ms 604 KB Output is correct
15 Correct 6 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 11 ms 912 KB Output is correct
18 Correct 9 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 12 ms 896 KB Output is correct
21 Correct 7 ms 756 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 2 ms 604 KB Output is correct
25 Correct 2 ms 688 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 12 ms 804 KB Output is correct
28 Correct 10 ms 860 KB Output is correct
29 Correct 7 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 11 ms 912 KB Output is correct
32 Correct 8 ms 604 KB Output is correct
33 Correct 232 ms 11672 KB Output is correct
34 Execution timed out 2100 ms 22144 KB Time limit exceeded
35 Halted 0 ms 0 KB -