Submission #1208196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208196		sangeraf	Unique Cities (JOI19_ho_t5)	C++20	0 / 100	76 ms	13640 KiB

joi2019_ho_t5

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

const int MAXN = 200001;

vector<vector<int>> G(MAXN);

int hossz = 0, kozep = 0;
vector<int> d(MAXN, -1);

int furthest(int v, int p = 0, int dakt = 0){
    d[v] = dakt;
    int dmax = dakt, vmax = v;
    for(int x : G[v]){
        if(x == p) continue;
        int maxi = furthest(x, v, dakt + 1);
        if(d[maxi] + 1 > dmax){
            dmax = d[maxi];
            vmax = maxi;
        }
    }
    hossz = max(hossz, dmax);
    return vmax;
}

void kozepkeres(int v, int p = 0, int dakt = 0){
    if(abs(dakt - d[v]) <= 1 && dakt + d[v] == hossz) kozep = v;
    for(int x : G[v]){
        if(x == p) continue;
        kozepkeres(x, v, dakt + 1);
    }
}

vector<int> unitav(MAXN, 0), melyseg(MAXN, 0);

void unikeres(int v, int p = 0){
    for(int x : G[v]){
        if(x == p) continue;

        unikeres(x, v);

        if(melyseg[x] + 1 >= unitav[v]){
            unitav[v] = 0;
            if(unitav[x] + 1 > melyseg[v]) unitav[v] = unitav[x] + 1;
            melyseg[v] = max(melyseg[v], melyseg[x] + 1);
        }
    }
}

vector<int> ans(MAXN, 0);

void szamol(int v, int p, int felunitav){
    if(melyseg[v] < felunitav) ans[v]++;
    for(int x : G[v]){
        if(x == p) continue;
        szamol(x, v, felunitav + 1);
    }
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

	int n, m; cin >> n >> m;

    if(n == 2){
        cout << "1\n1\n";
        return 0;
    }

    for(int i=0; i<n-1; i++){
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    kozepkeres(furthest(furthest(1)));

    unikeres(kozep);

    if(unitav[kozep] > 0) ans[kozep]++;

    int mely1=-1, mely2=-1, maximely=-1, uni1=0, uni2=0, fa1=0, fa2=0;

    for(int x : G[kozep]){
        if(melyseg[x] > mely2){
            maximely = max(maximely, mely2);
            mely2 = melyseg[x];
            uni2 = unitav[x];
            fa2 = x;
            if(mely2 > mely1){
                swap(mely1, mely2);
                swap(uni1, uni2);
                swap(fa1, fa2);
            }
        }else{
            maximely = max(maximely, melyseg[x]);
        }
    }

    /*cout << maximely << endl;
    cout << mely1 << " " << uni1 << " " << fa1 << endl;
    cout << mely2 << " " << uni2 << " " << fa2 << endl;*/

    if(maximely >= uni1) uni1 = -1;
    if(maximely >= uni2) uni2 = -1;

    szamol(fa1, kozep, uni2 + 2);
    szamol(fa2, kozep, uni1 + 2);

    if(mely2 >= uni1) uni1 = -1;

    for(int x : G[kozep]){
        if(x == fa1 || x == fa2) continue;
        szamol(x, kozep, uni1 + 2);
    }

    for(int i=1; i<=n; i++){
        cout << ans[i] << "\n";
    }
    /*for(int i=1; i<=n; i++) cout << d[i] << " "; cout << endl;
    cout << hossz << " " << kozep << endl;
    for(int i=1; i<=n; i++) cout << melyseg[i] << " "; cout << endl;
    for(int i=1; i<=n; i++) cout << unitav[i] << " "; cout << endl;*/
}

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