Submission #1208189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208189		algoproclub	Unique Cities (JOI19_ho_t5)	C++20	0 / 100	77 ms	11844 KiB

joi2019_ho_t5

// UUID: bec675e6-697d-41bc-838a-f4ef46168c70
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;

int vv, dv;
int a, b, hossz, kozep;
vector<int> d;

void furthest(int v, int p = 0){
    d[v] = d[p] + 1;
    if(d[v] > dv){
        vv = v;
        dv = d[v];
    }
    for(int x : G[v]){
        if(x == p) continue;
        furthest(x, v);
    }
}

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

vector<int> unitav, melyseg;

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;

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;
    }
    G.resize(n+1);
    for(int i=0; i<n-1; i++){
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vv = dv = 0;
    d.assign(n+1, -1);
    furthest(1);
    a = vv;
    vv = dv = 0;
    d.assign(n+1, -1);
    furthest(a);
    b = vv;
    hossz = dv;
    kozepkeres(b);

    // atmero: a -> b; kozep; hossz
    unitav.resize(n+1, 0);
    melyseg.resize(n+1, 0);
    unikeres(kozep);

    ans.resize(n+1, 0);
    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";
    }
}

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