Submission #423262

#	Time	Username	Problem	Language	Result	Execution time	Memory
423262		Kerim	Unique Cities (JOI19_ho_t5)	C++17	100 / 100	574 ms	55564 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;
 
const int N = 200000;
 
int color[N], depth[N];
vector<int> adj[N];
 
void dfs_depth(int u, int p = -1) {
    for (auto c : adj[u]) {
        if (c != p) {
            depth[c] = depth[u] + 1;
            dfs_depth(c, u);
        }
    }
}
 
int height[N];
 
void dfs_height(int u, int p = -1) {
    height[u] = 0;
    for (auto c : adj[u]) {
        if (c != p) {
            dfs_height(c, u);
            height[u] = max(height[u], height[c] + 1);
        }
    }
}
 
int tally[N], ans[N], k;
vector<int> path;
 
void trim(int u, int d) {
    while (!path.empty() && depth[u] - depth[path.back()] <= d) {
        k -= --tally[color[path.back()]] == 0;
        path.pop_back();
    }
}
 
void dfs_unique(int u, int p = -1) {
    vector<array<int, 2>> children;
    for (auto c : adj[u]) {
        if (c != p) {
            children.push_back({height[c], c});
        }
    }
    sort(children.rbegin(), children.rend());
 
    if (!children.empty()) {
        if (children.size() > 1) {
            trim(u, children[1][0] + 1);
        }
		bool f=0;
        for (auto [h, c] : children) {
            k += ++tally[color[u]] == 1;
            path.push_back(u);
 
            dfs_unique(c, u);
 
            if (!path.empty() && path.back() == u) {
                k -= --tally[color[u]] == 0;
                path.pop_back();
            }
            if(!f)
				trim(u, h + 1),f=1;
        }
    }
 
    ans[u] = max(ans[u], k);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
 
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    for (int i = 0; i < n; ++i) {
        cin >> color[i];
        --color[i];
    }
 
    dfs_depth(0);
 
    for (int i = 0; i < 2; ++i) {
        int root = max_element(depth, depth + n) - depth;
        depth[root] = 0;
        dfs_depth(root);
        dfs_height(root);
        dfs_unique(root);
    }
 
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << "\n";
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32