oj.uz

Submission #423111

# Submission time Handle Problem Language Result Execution time Memory
423111 2021-06-10T17:44:51 Z Kerim Unique Cities (JOI19_ho_t5) C++17
0 / 100
 293 ms 16400 KB 
#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);
        }
 
        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(children.size() ==1)
				trim(u, h + 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Incorrect 5 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 12348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 16400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Incorrect 5 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -