Submission #881625

#TimeUsernameProblemLanguageResultExecution timeMemory
881625tsumondaiUnique Cities (JOI19_ho_t5)C++14
100 / 100
328 ms49284 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, r, l) for(int i = r; i >= l; i--) #define __TIME (1.0 * clock() / CLOCKS_PER_SEC) typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 2e5 + 5; const int oo = 1e9, mod = 1e9 + 7; int n, m, k, color[N], ptr; string s; vector<int> adj[N]; int dp[N], depth[N]; void dfs_len(int u, int p = 0) { dp[u] = depth[u] = depth[p] + 1; if (depth[ptr] < depth[u]) ptr = u; for (int v : adj[u]) if (v != p) { dfs_len(v, u); dp[u] = max(dp[u], dp[v]); } } int cnt[N], cnt_unique, ans[N]; vector<int> A; void add(int x) { if (++cnt[color[x]] == 1) ++cnt_unique; A.push_back(x); } void del() { int x = A.back(); A.pop_back(); if (--cnt[color[x]] == 0) --cnt_unique; } void dfs(int u, int p = 0) { if (p) add(p); vector<ii> vec; for (int v : adj[u]) if (v != p) vec.emplace_back(dp[v], v); sort(vec.begin(), vec.end(), greater<ii>()); int mx1 = vec.size() > 0 ? vec[0].fi : 0; int mx2 = vec.size() > 1 ? vec[1].fi : 0; for (ii v : vec) { int mx = mx1 + mx2 - max(v.fi, mx2); while (!A.empty() && mx - depth[u] >= depth[u] - depth[A.back()]) del(); dfs(v.se, u); } while (!A.empty() && dp[u] - depth[u] >= depth[u] - depth[A.back()]) del(); ans[u] = max(ans[u], cnt_unique); } void process() { cin >> n >> m; foru(i,1,n-1) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } foru(i,1,n) cin >> color[i]; dfs_len(ptr=1); int i; foru(k,0,1) { dfs_len(i=ptr); dfs(i); } foru(i,1,n) cout << ans[i] << ' '; return; } signed main() { cin.tie(0)->sync_with_stdio(false); //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); process(); cerr << "Time elapsed: " << __TIME << " s.\n"; return 0; } /* Xét các trường hợp đặc biệt Kiểm tra lại input/output Cố gắng trâu Lật ngược bài toán Keep calm and get VOI Flow: */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...