Submission #749634

#TimeUsernameProblemLanguageResultExecution timeMemory
749634stevancvCapital City (JOI20_capital_city)C++14
100 / 100
368 ms87116 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 2e5 + 2; const int inf = 1e9; vector<int> g[N]; int par[N][18], in[N], out[N], tsz; void Dfs(int s, int e) { in[s] = ++tsz; par[s][0] = e; for (int i = 1; i < 18; i++) par[s][i] = par[par[s][i - 1]][i - 1]; for (int u : g[s]) { if (u == e) continue; Dfs(u, s); } out[s] = tsz; } bool Ancestor(int u, int v) { return in[u] <= in[v] && out[v] <= out[u]; } int Lca(int u, int v) { if (Ancestor(u, v)) return u; if (Ancestor(v, u)) return v; for (int i = 17; i >= 0; i--) { if (par[u][i] && !Ancestor(par[u][i], v)) u = par[u][i]; } return par[u][0]; } int c[N], predak[N]; vector<int> boja[N]; set<int> koji[N]; void Dfs1(int s, int e) { for (int u : g[s]) { if (u == e) continue; if (c[s] != c[u] && Ancestor(predak[c[u]], s)) koji[c[u]].insert(c[s]); Dfs1(u, s); } } vector<int> a[N], b[N], order; int visited[N], id[N], szk[N], brk; void Dfs2(int s) { if (visited[s] == 1) return; visited[s] = 1; for (int u : a[s]) { Dfs2(u); } order.push_back(s); } void Dfs3(int s) { if (id[s] > 0) return; id[s] = brk; szk[brk] += 1; for (int u : b[s]) { Dfs3(u); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k; 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); } Dfs(1, 0); for (int i = 1; i <= n; i++) { cin >> c[i]; boja[c[i]].push_back(i); } for (int i = 1; i <= k; i++) { predak[i] = boja[i][0]; for (int j = 1; j < boja[i].size(); j++) predak[i] = Lca(predak[i], boja[i][j]); } Dfs1(1, 0); for (int i = 1; i <= k; i++) { for (int j : koji[i]) { a[i].push_back(j); b[j].push_back(i); } } for (int i = 1; i <= k; i++) { if (visited[i] == 0) { Dfs2(i); } } reverse(order.begin(), order.end()); for (int i : order) { if (id[i] == 0) { brk += 1; Dfs3(i); } } vector<int> cnt(brk + 1); for (int i = 1; i <= k; i++) { for (int j : a[i]) { if (id[i] != id[j]) { cnt[id[i]] += 1; } } } int ans = inf; for (int i = 1; i <= brk; i++) if (cnt[i] == 0) smin(ans, szk[i] - 1); cout << ans << en; return 0; }

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int j = 1; j < boja[i].size(); j++) predak[i] = Lca(predak[i], boja[i][j]);
      |                         ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...