oj.uz

Submission #99277

# Submission time Handle Problem Language Result Execution time Memory
99277 2019-03-02T04:54:15 Z imeimi2000 Unique Cities (JOI19_ho_t5) C++17
32 / 100
 722 ms 28828 KB 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
vector<int> edge[200001];
int col[200001];
int dist[200001];
int dep[200001];

void dfs1(int x, int p) {
    dist[x] = dist[p] + 1;
    for (int i : edge[x]) {
        if (i == p) continue;
        dfs1(i, x);
    }
}

int ans[200001];

void dfs2(int x, int p) {
    dist[x] = dist[p] + 1;
    dep[x] = 0;
    for (int i : edge[x]) {
        if (i == p) continue;
        dfs2(i, x);
        dep[x] = max(dep[x], dep[i] + 1);
    }
}

vector<int> st;
int cnt[200001];
int sum;

void add(int x, int v) {
    x = col[x];
    if (cnt[x] == 0) ++sum;
    cnt[x] += v;
    if (cnt[x] == 0) --sum;
}

void dfs3(int x, int p) {
    int mx1 = -1, mx2 = -1;
    for (int i : edge[x]) {
        if (i == p) continue;
        if (mx1 < dep[i]) mx2 = mx1, mx1 = dep[i];
        else if (mx2 < dep[i]) mx2 = dep[i];
    }
    int mxi = 0;
    for (int i : edge[x]) {
        if (i == p) continue;
        if (dep[i] == mx1) {
            mxi = i;
            break;
        }
    }
    ++mx1; ++mx2;
    while (!st.empty() && dist[x] - dist[st.back()] <= mx2) {
        add(st.back(), -1);
        st.pop_back();
    }
    if (mxi) {
        add(x, 1);
        st.push_back(x);
        dfs3(mxi, x);
    }
    while (!st.empty() && dist[x] - dist[st.back()] <= mx1) {
        add(st.back(), -1);
        st.pop_back();
    }
    ans[x] = max(ans[x], sum);
    for (int i : edge[x]) {
        if (i == p || i == mxi) continue;
        if (st.empty() || st.back() != x) {
            add(x, 1);
            st.push_back(x);
        }
        dfs3(i, x);
    }
}

void solve(int R) {
    dfs2(R, 0);
    st.clear();
    sum = 0;
    for (int i = 1; i <= m; ++i) cnt[i] = 0;
    dfs3(R, 0);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) cin >> col[i];
    dfs1(1, 0);
    int P = max_element(dist + 1, dist + (n + 1)) - dist;
    dfs1(P, 0);
    int Q = max_element(dist + 1, dist + (n + 1)) - dist;
    solve(P); solve(Q);
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 8 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 11128 KB Output is correct
2 Correct 351 ms 19000 KB Output is correct
3 Correct 57 ms 7672 KB Output is correct
4 Correct 514 ms 15480 KB Output is correct
5 Correct 668 ms 28828 KB Output is correct
6 Correct 722 ms 21924 KB Output is correct
7 Correct 517 ms 15496 KB Output is correct
8 Correct 586 ms 16716 KB Output is correct
9 Correct 534 ms 16520 KB Output is correct
10 Correct 532 ms 16412 KB Output is correct
11 Correct 260 ms 16236 KB Output is correct
12 Correct 640 ms 23768 KB Output is correct
13 Correct 548 ms 22072 KB Output is correct
14 Correct 543 ms 21492 KB Output is correct
15 Correct 276 ms 16240 KB Output is correct
16 Correct 546 ms 24776 KB Output is correct
17 Correct 648 ms 22508 KB Output is correct

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 8 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -