oj.uz

Submission #220203

# Submission time Handle Problem Language Result Execution time Memory
220203 2020-04-07T10:13:14 Z fedoseevtimofey Capital City (JOI20_capital_city) C++14
11 / 100
 3000 ms 524288 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;
const int M = 4e6 + 7;

vector <int> g[N];
int col[N];

bool used[N];

int dfs(int u, int size, int &c, int p = -1) {
  int sum = 1;
  for (auto v : g[u]) {
    if (!used[v] && v != p) {
      sum += dfs(v, size, c, u);
    }
  }
  if (c == -1 && (2 * sum >= size || p == -1)) {
    c = u;
  }
  return sum;
}

int uk;

vector <int> gr[M];
vector <int> rg[M];

int num[N];
vector <int> who[N];

void add(int u, int v) {
  gr[u].push_back(v);
  rg[v].push_back(u);
}


vector <int> subtr;

void solve(int u, int p = -1) {
  subtr.push_back(u);
  for (auto v : g[u]) {
    if (!used[v] && v != p) {
      num[v] = uk++;
      add(num[v], col[v]);
      add(num[v], num[u]);
      solve(v, u);
    }
  }
}

int timer = 0;
int cur_cnt[N];
int last_seen[N];

void build(int u, int size, int last) {
  int c = -1; 
  dfs(u, size, c);
  used[c] = true;
  num[c] = uk++;
  add(num[c], col[c]);
  vector <vector <int>> cmp;
  for (auto v : g[c]) {
    if (!used[v]) {
      num[v] = uk++;
      add(num[v], col[v]);
      add(num[v], num[c]);

      subtr.clear();
      solve(v, c);
      cmp.push_back(subtr);
    }
  }
  cmp.push_back({c});
  for (auto sb : cmp) {
    ++timer;
    for (auto v : sb) {
      who[col[v]].push_back(v);
      if (last_seen[col[v]] != timer) {
        last_seen[col[v]] = timer;
        ++cur_cnt[col[v]];
      }
    }
  }

  for (auto sb : cmp) {
    for (auto v : sb) {
      if (cur_cnt[col[v]] > 1) {
        for (auto vr : who[col[v]]) {
          add(col[v], num[vr]);
        }
      }
      who[col[v]] = {};
      cur_cnt[col[v]] = 0;
    }
  }

  cmp = {};
   
  for (auto v : g[c]) {
    if (!used[v]) {
      build(v, (size + 1) / 2, c);
    }
  }
}


vector <int> t;
int cmp[M];
int sz[M];
bool hv[M];

void get_topsort(int u) {
  used[u] = true;
  for (auto v : gr[u]) {
    if (!used[v]) {
      get_topsort(v);
    }
  }
  t.push_back(u);
}

int cnt = 0;

int k;

void jhfs(int u) {
  used[u] = true;
  cmp[u] = cnt;
  if (u < k) ++sz[cnt];
  for (auto v : rg[u]) {
    if (!used[v]) {
      jhfs(v);
    }
  }
}

int ans;

void zhfs(int u) {
  used[u] = true;
  for (auto v : rg[u]) {
    if (!used[v]) {
      zhfs(v);
    }
    cmp[u] |= cmp[v];
  }
  if (!cmp[u] && sz[u] > 0) {
    ans = min(ans, sz[u]);
  }
  if (sz[u] > 0) cmp[u] = 1;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n >> k;
  for (int i = 0; i + 1 < n; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 0; i < n; ++i) {
    cin >> col[i];
    --col[i];
  }

  uk = k;
  build(0, n, -1);
  
 
  fill(used, used + uk, false);
  for (int i = 0; i < uk; ++i) {
    if (!used[i]) {
      get_topsort(i);
    }
  }
  reverse(t.begin(), t.end());
  fill(used, used + uk, false);   
  for (int u : t) {
    if (!used[u]) {
      jhfs(u);
      ++cnt;
    }
  }
  for (int i = 0; i < uk; ++i) rg[i] = {};
  for (int i = 0; i < uk; ++i) {
    for (auto v : gr[i]) {
      if (cmp[i] != cmp[v]) {
        rg[cmp[i]].push_back(cmp[v]);
      }
    }
  }
  for (int i = 0; i < cnt; ++i) {
    sort(rg[i].begin(), rg[i].end());
    rg[i].resize(unique(rg[i].begin(), rg[i].end()) - rg[i].begin());
  }
  ans = n;
  fill(used, used + cnt, 0);
  for (int i = 0; i < cnt; ++i) cmp[i] = 0;
  for (int i = 0; i < cnt; ++i) {
    if (!used[i]) {
      zhfs(i);
    }
  }
  cout << ans - 1 << '\n';
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 197624 KB Output is correct
2 Correct 112 ms 197624 KB Output is correct
3 Correct 112 ms 197624 KB Output is correct
4 Correct 117 ms 197600 KB Output is correct
5 Correct 111 ms 197624 KB Output is correct
6 Correct 117 ms 197696 KB Output is correct
7 Correct 111 ms 197624 KB Output is correct
8 Correct 121 ms 197860 KB Output is correct
9 Correct 114 ms 197624 KB Output is correct
10 Correct 121 ms 197624 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 197624 KB Output is correct
2 Correct 112 ms 197624 KB Output is correct
3 Correct 112 ms 197624 KB Output is correct
4 Correct 117 ms 197600 KB Output is correct
5 Correct 111 ms 197624 KB Output is correct
6 Correct 117 ms 197696 KB Output is correct
7 Correct 111 ms 197624 KB Output is correct
8 Correct 121 ms 197860 KB Output is correct
9 Correct 114 ms 197624 KB Output is correct
10 Correct 121 ms 197624 KB Output is correct
11 Correct 122 ms 198776 KB Output is correct
12 Correct 131 ms 199032 KB Output is correct
13 Correct 123 ms 198904 KB Output is correct
14 Correct 118 ms 198868 KB Output is correct
15 Correct 127 ms 199292 KB Output is correct
16 Correct 128 ms 199196 KB Output is correct
17 Correct 127 ms 198940 KB Output is correct
18 Correct 122 ms 198880 KB Output is correct
19 Correct 119 ms 198904 KB Output is correct
20 Correct 121 ms 198904 KB Output is correct
21 Correct 126 ms 198904 KB Output is correct
22 Correct 122 ms 199544 KB Output is correct
23 Correct 134 ms 199544 KB Output is correct
24 Correct 122 ms 199288 KB Output is correct
25 Correct 126 ms 199596 KB Output is correct
26 Correct 120 ms 199544 KB Output is correct
27 Correct 125 ms 199544 KB Output is correct
28 Correct 124 ms 199288 KB Output is correct
29 Correct 123 ms 199520 KB Output is correct
30 Correct 127 ms 199448 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3105 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 197624 KB Output is correct
2 Correct 112 ms 197624 KB Output is correct
3 Correct 112 ms 197624 KB Output is correct
4 Correct 117 ms 197600 KB Output is correct
5 Correct 111 ms 197624 KB Output is correct
6 Correct 117 ms 197696 KB Output is correct
7 Correct 111 ms 197624 KB Output is correct
8 Correct 121 ms 197860 KB Output is correct
9 Correct 114 ms 197624 KB Output is correct
10 Correct 121 ms 197624 KB Output is correct
11 Correct 122 ms 198776 KB Output is correct
12 Correct 131 ms 199032 KB Output is correct
13 Correct 123 ms 198904 KB Output is correct
14 Correct 118 ms 198868 KB Output is correct
15 Correct 127 ms 199292 KB Output is correct
16 Correct 128 ms 199196 KB Output is correct
17 Correct 127 ms 198940 KB Output is correct
18 Correct 122 ms 198880 KB Output is correct
19 Correct 119 ms 198904 KB Output is correct
20 Correct 121 ms 198904 KB Output is correct
21 Correct 126 ms 198904 KB Output is correct
22 Correct 122 ms 199544 KB Output is correct
23 Correct 134 ms 199544 KB Output is correct
24 Correct 122 ms 199288 KB Output is correct
25 Correct 126 ms 199596 KB Output is correct
26 Correct 120 ms 199544 KB Output is correct
27 Correct 125 ms 199544 KB Output is correct
28 Correct 124 ms 199288 KB Output is correct
29 Correct 123 ms 199520 KB Output is correct
30 Correct 127 ms 199448 KB Output is correct
31 Execution timed out 3105 ms 524288 KB Time limit exceeded
32 Halted 0 ms 0 KB -