Submission #1217291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217291		JooDdae	Unique Cities (JOI19_ho_t5)	C++20	32 / 100	184 ms	37652 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, c[200200], d[200200], ans[200200], h[200200];
vector<int> v[200200];

int dfs(int u, int p) {
    h[u] = 1, d[u] = d[p]+1;
    for(auto x : v[u]) if(x != p) h[u] = max(h[u], dfs(x, u)+1);
    return h[u];
}

vector<int> st;

void dfs2(int u, int p) {
    if(p && v[u].size() == 1) {
        // cout << u << "\n";
        // for(auto x : st) cout << x << "]\n";
        ans[u] = max(ans[u], (int)st.size());
        return;
    }

    int C = !!p;
    sort(v[u].begin(), v[u].end(), [&](int a, int b){ return h[a] > h[b]; });
    while(v[u].size() > 2 && !st.empty() && d[u]-d[st.back()] <= h[v[u][2]]) st.pop_back();
    st.push_back(u);
    dfs2(v[u][C], u);

    while(!st.empty() && d[u]-d[st.back()] <= h[v[u][C]]) st.pop_back();
    ans[u] += st.size();

    for(int i=C+1;i<v[u].size();i++) {
        while(!st.empty() && d[st.back()] >= d[u]) st.pop_back();
        st.push_back(u);
        dfs2(v[u][i], u);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<n;i++) {
        int x, y; cin >> x >> y;
        v[x].push_back(y), v[y].push_back(x);
    }
    for(int i=1;i<=n;i++) cin >> c[i];

    dfs(1, 0);
    int L = max_element(d+1, d+1+n) - d;
    dfs(L, 0);
    int R = max_element(d+1, d+1+n) - d;

    for(auto r : {L, R}) 
        st.clear(), dfs(r, 0), dfs2(r, 0);

    for(int i=1;i<=n;i++) cout << min(1, ans[i]) << "\n";
}

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