oj.uz

Submission #220199

# Submission time Handle Problem Language Result Execution time Memory
220199 2020-04-07T10:07:50 Z fedoseevtimofey Capital City (JOI20_capital_city) C++14
11 / 100
 1712 ms 524292 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]].clear();
      cur_cnt[col[v]] = 0;
    }
  }

  cmp.clear();

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


vector <int> t;
int cmp[M];
int sz[M];
vector <int> gc[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 : gc[u]) {
    if (!used[v]) {
      zhfs(v);
    }
    hv[u] |= hv[v];
  }
  if (!hv[u] && sz[u] > 0) {
    ans = min(ans, sz[u]);
  }
  if (sz[u] > 0) hv[u] = true;
}

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) {
    for (auto v : gr[i]) {
      if (cmp[i] != cmp[v]) {
        gc[cmp[i]].push_back(cmp[v]);
      }
    }
  }
  for (int i = 0; i < cnt; ++i) {
    sort(gc[i].begin(), gc[i].end());
    gc[i].resize(unique(gc[i].begin(), gc[i].end()) - gc[i].begin());
  }
  ans = n;
  fill(used, used + cnt, 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 161 ms 291632 KB Output is correct
2 Correct 167 ms 291704 KB Output is correct
3 Correct 163 ms 291580 KB Output is correct
4 Correct 161 ms 291576 KB Output is correct
5 Correct 160 ms 291508 KB Output is correct
6 Correct 161 ms 291576 KB Output is correct
7 Correct 172 ms 291576 KB Output is correct
8 Correct 158 ms 291576 KB Output is correct
9 Correct 162 ms 291708 KB Output is correct
10 Correct 159 ms 291576 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 291632 KB Output is correct
2 Correct 167 ms 291704 KB Output is correct
3 Correct 163 ms 291580 KB Output is correct
4 Correct 161 ms 291576 KB Output is correct
5 Correct 160 ms 291508 KB Output is correct
6 Correct 161 ms 291576 KB Output is correct
7 Correct 172 ms 291576 KB Output is correct
8 Correct 158 ms 291576 KB Output is correct
9 Correct 162 ms 291708 KB Output is correct
10 Correct 159 ms 291576 KB Output is correct
11 Correct 166 ms 292984 KB Output is correct
12 Correct 182 ms 293112 KB Output is correct
13 Correct 171 ms 293112 KB Output is correct
14 Correct 173 ms 292984 KB Output is correct
15 Correct 173 ms 293496 KB Output is correct
16 Correct 170 ms 293368 KB Output is correct
17 Correct 168 ms 292856 KB Output is correct
18 Correct 167 ms 292856 KB Output is correct
19 Correct 172 ms 292900 KB Output is correct
20 Correct 167 ms 292856 KB Output is correct
21 Correct 168 ms 292856 KB Output is correct
22 Correct 176 ms 294012 KB Output is correct
23 Correct 174 ms 293880 KB Output is correct
24 Correct 177 ms 293624 KB Output is correct
25 Correct 173 ms 293492 KB Output is correct
26 Correct 175 ms 293532 KB Output is correct
27 Correct 170 ms 293532 KB Output is correct
28 Correct 171 ms 293476 KB Output is correct
29 Correct 169 ms 293368 KB Output is correct
30 Correct 168 ms 293368 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1712 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 291632 KB Output is correct
2 Correct 167 ms 291704 KB Output is correct
3 Correct 163 ms 291580 KB Output is correct
4 Correct 161 ms 291576 KB Output is correct
5 Correct 160 ms 291508 KB Output is correct
6 Correct 161 ms 291576 KB Output is correct
7 Correct 172 ms 291576 KB Output is correct
8 Correct 158 ms 291576 KB Output is correct
9 Correct 162 ms 291708 KB Output is correct
10 Correct 159 ms 291576 KB Output is correct
11 Correct 166 ms 292984 KB Output is correct
12 Correct 182 ms 293112 KB Output is correct
13 Correct 171 ms 293112 KB Output is correct
14 Correct 173 ms 292984 KB Output is correct
15 Correct 173 ms 293496 KB Output is correct
16 Correct 170 ms 293368 KB Output is correct
17 Correct 168 ms 292856 KB Output is correct
18 Correct 167 ms 292856 KB Output is correct
19 Correct 172 ms 292900 KB Output is correct
20 Correct 167 ms 292856 KB Output is correct
21 Correct 168 ms 292856 KB Output is correct
22 Correct 176 ms 294012 KB Output is correct
23 Correct 174 ms 293880 KB Output is correct
24 Correct 177 ms 293624 KB Output is correct
25 Correct 173 ms 293492 KB Output is correct
26 Correct 175 ms 293532 KB Output is correct
27 Correct 170 ms 293532 KB Output is correct
28 Correct 171 ms 293476 KB Output is correct
29 Correct 169 ms 293368 KB Output is correct
30 Correct 168 ms 293368 KB Output is correct
31 Runtime error 1712 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -