Submission #1027376

#TimeUsernameProblemLanguageResultExecution timeMemory
1027376adaawfCapital City (JOI20_capital_city)C++17
1 / 100
257 ms46540 KiB
#include <iostream> #include <vector> #include <queue> using namespace std; vector<int> g[200005], v[200005], vv; int c[200005], dd[200005], da[200005], db[200005], a[200005]; int tn[200005], tt[200005], d[200005], s[200005], z = 0; void dfs(int x, int p) { tn[x] = ++z; s[x] = 1; c[a[x]]++; d[x] = p; for (int w : g[x]) { if (w == p || dd[w] == 1) continue; dfs(w, x); s[x] += s[w]; } tt[x] = z; } void dfs2(int x, int p) { da[a[x]] = db[x] = c[a[x]] = 0; for (int w : g[x]) { if (w == p || dd[w] == 1) continue; dfs2(w, x); } } int centroid(int x, int p, int h) { for (int w : g[x]) { if (w == p || dd[w] == 1) continue; if (s[w] > h / 2) { return centroid(w, x, h); } } return x; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k, mi = 1e9; cin >> n >> k; 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 >> a[i]; v[a[i]].push_back(i); } queue<int> q; q.push(1); while (!q.empty()) { int p = q.front(); q.pop(); if (dd[p] == 1) continue; z = 0; dfs(p, -1); int h = centroid(p, -1, s[p]), flag = 0, k = h, res = 0; vv.push_back(a[h]); da[a[h]] = 1; for (int i = 0; i < vv.size(); i++) { int w = vv[i]; if (c[w] != v[w].size()) { flag = 1; break; } res++; for (int ww : v[w]) { while (tn[k] > tn[ww] || tt[k] < tt[ww]) { k = d[k]; db[k] = 1; if (da[a[k]] == 0) { vv.push_back(a[k]); da[a[k]] = 1; } } int h = ww; while (db[h] == 0 && h != d[k]) { if (da[a[h]] == 0) { vv.push_back(a[h]); da[a[h]] = 1; } db[h] = 1; h = d[h]; } } } if (flag == 0) mi = min(mi, res - 1); dfs2(p, -1); dd[h] = 1; for (int w : g[h]) { if (dd[w] == 0) { q.push(w); } } } cout << mi; }

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int i = 0; i < vv.size(); i++) {
      |                         ~~^~~~~~~~~~~
capital_city.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             if (c[w] != v[w].size()) {
      |                 ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...