oj.uz

Submission #773553

# Submission time Handle Problem Language Result Execution time Memory
773553 2023-07-05T06:43:12 Z 1bin Unique Cities (JOI19_ho_t5) C++14
0 / 100
 2000 ms 14852 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
int n, m, C[NMAX], D[NMAX], a, b, mxd, ix, r1, r2, ans[NMAX], cur, cnt[NMAX], mx[NMAX][2], idx[NMAX][2];
vector<int> adj[NMAX];

void dfs2(int x, int p, int d){
    if(d > mxd) mxd = d, ix = x;
    for(int&nx : adj[x])
        if(nx != p) dfs2(nx, x, d + 1);
    return;
}

void go(int x, int p){
    mx[x][0] = mx[x][1] = 0;
    for(int& nx : adj[x])
        if(nx != p){
            go(nx, x);
            if(mx[nx][0] + 1 > mx[x][1]) mx[x][1] = mx[nx][0] + 1, idx[x][1] = nx;
            if(mx[x][0] < mx[x][1]){
                swap(mx[x][0], mx[x][1]);
                swap(idx[x][0], idx[x][1]);
            }
        }
    return;
}

void f(int x, int add){
    if(add){
        if(++cnt[C[x]] == 1) cur++;
    }
    else{
        if(--cnt[C[x]] == 0) cur--;
    }
    return;
}

stack<int> st;
void dfs(int x, int p, int d){
    stack<int> t;
    D[d] = x;
    
    auto calc = [&] (int mxd){
        while(st.size() && st.top() >= mxd){
            f(D[st.top()], 0);
            t.emplace(st.top()); st.pop();
        }
    };
    if(mx[x][0]){
        int nx = idx[x][0];
        if(mx[x][1]) calc(d - mx[x][1]);
        st.emplace(d); f(x, 1);
        dfs(nx, x, d + 1);
        st.pop(); f(x, 0);
        
        calc(d - mx[x][0]);
        for(int& nx : adj[x])
            if(nx != p && nx != mx[x][0]){
                st.emplace(d); f(x, 1);
                dfs(nx, x, d + 1);
                st.pop(); f(x, 0);
            }
    }
    ans[x] = max(ans[x], cur);
    while(t.size()){
        f(D[t.top()], 1);
        st.emplace(t.top()); t.pop();
    }
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for(int i = 1; i < n; i++){
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }    
    for(int i = 1; i <= n; i++) cin >> C[i];
    dfs2(1, -1, 0);
    r1 = ix;
    mxd = 0; dfs2(r1, -1, 0);
    r2 = ix;
    
    go(r1, -1); dfs(r1, -1, 0);
    go(r2, -1); dfs(r2, -1, 0);
    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Execution timed out 2066 ms 5172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 11892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 14852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Execution timed out 2066 ms 5172 KB Time limit exceeded
3 Halted 0 ms 0 KB -