제출 #1321125

#제출 시각아이디문제언어결과실행 시간메모리
1321125ivan_alexeevUnique Cities (JOI19_ho_t5)C++20
0 / 100
114 ms13072 KiB
#include <bits/stdc++.h>

using namespace std;

#ifndef lisie_bimbi
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
#endif

using ll = long long;
const ll inf = 1'000'000'000;

vector<vector<int>> v;
vector<int> c;

pair<int, int> furthest(int u, int par){
    int mx = 0, z = u;
    for(auto i : v[u]){
        if(i != par){
            auto [mx2, z2] = furthest(i, u);
            if(mx2 + 1 > mx){
                mx = mx2 + 1;
                z = z2;
            }
        }
    }
    return {mx, z};
}

void calcdist(int u, int par, vector<int> &d){
    if(par == -1){
        d[u] = 0;
    }else{
        d[u] = d[par] + 1;
    }
    for(auto i : v[u]){
        if(i != par){
            calcdist(i, u, d);
        }
    }
}

void calcleaf(int u, int par, vector<int> &d){
    for(auto i : v[u]){
        if(i != par){
            calcleaf(i, u, d);
            d[u] = max(d[u], d[i] + 1);
        }
    }
}

int n;

void calcans(int u, int par, int level, int NOW, vector<int> &d, vector<int> &ans){
    if(NOW + d[u] < level){
        ans[u] = 1;
    }
    int mx1 = 0, mx2 = 0;
    for(auto i : v[u]){
        if(i != par){
            if(d[i] > mx1){
                mx2 = mx1;
                mx1 = d[i];
            }else if(d[i] > mx2){
                mx2 = d[i];
            }
        }
    }
    for(auto i : v[u]){
        if(i != par){
            if(d[i] != mx1){
                if(NOW + mx1 < level){
                    calcans(i, u, level + 1, NOW, d, ans);
                }else{
                    calcans(i, u, level + 1, level, d, ans);
                }
            }else{
                if(NOW + mx2 < level){
                    calcans(i, u, level + 1, NOW, d, ans);
                }else{
                    calcans(i, u, level + 1, level, d, ans);
                }
            }
        }
    }
}

vector<int> calc(int s){
    vector<int> a(n);
    calcleaf(s, -1, a);
    vector<int> ans(n);
    calcans(s, -1, 0, 0, a, ans);
    return ans;
}

void solve(){
    int m;
    cin >> n >> m;
    v.resize(n);
    for(int i = 0; i < n - 1; i++){
        int x, y;
        cin >> x >> y;
        x--;y--;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    c.resize(n);
    for(int i = 0; i < n; i++){
        cin >> c[i];
    }
    auto [_, s1] = furthest(0, -1);
    auto [__, s2] = furthest(s1, -1);
    vector<int> d1(n), d2(n);
    calcdist(s1, -1, d1);
    calcdist(s2, -1, d2);
    auto ans1 = calc(s1);
    auto ans2 = calc(s2);
    for(int i = 0; i < n; i++){
        if(d1[i] > d2[i]){
            cout << ans1[i] << endl;
        }else{
            cout << ans2[i] << endl;
        }
    }
}

signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
#endif
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...