Submission #589664

#	Time	Username	Problem	Language	Result	Execution time	Memory
589664		Peti	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	2719 ms	43704 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
vector<int> alatt;
vector<bool> volt;

int meret(int akt, int os){
    alatt[akt] = 1;
    for(int x : g[akt])
        if(!volt[x] && x != os)
            alatt[akt] += meret(x, akt);
    return alatt[akt];
}

int getc(int akt, int os, int m){
    for(int x : g[akt])
        if(!volt[x] && x != os && alatt[x]*2 > m)
            return getc(x, akt, m);
    return akt;
}

void upd(set<pair<int, int>> &s, pair<int, int> p){
    auto it = s.insert(p).first;
    if(next(it) != s.end() && next(it)->second >= it->second){
        s.erase(it);
    }else{
        while(it != s.begin() && prev(it)->second <= it->second)
            s.erase(prev(it));
    }
}

void bejar(set<pair<int, int>> &s1, set<pair<int, int>> &s2, int akt, int t, int os, int rem){
    auto it = s1.lower_bound({alatt[akt], 0});
    if(it != s1.end()){
        //cout<<"uj: "<<2*alatt[akt]<<' '<<t<<" | "<<it->first<<' '<<it->second<<'\n';
        upd(s2, {2*alatt[akt], t + it->second + 1});
    }
    upd(s2, {min(alatt[akt], rem)*2, t+1});
    for(int x : g[akt])
        if(!volt[x] && x != os)
            bejar(s1, s2, x, t+1, akt, rem);
}

void berak(set<pair<int, int>> &s, int akt, int t, int os){
    //cout<<"berak: "<<akt<<' '<<alatt[akt]<<'\n';
    upd(s, {alatt[akt], t});
    for(int x : g[akt])
        if(!volt[x] && x != os)
            berak(s, x, t+1, akt);
}

vector<int> ki;
void decomposition(int c){
    c = getc(c, -1, meret(c, -1));
    volt[c] = true;
    meret(c, -1);

    set<pair<int, int>> s1, s2;
    for(int x : g[c]){
        if(!volt[x]){
            bejar(s1, s2, x, 1, c, alatt[c] - alatt[x]);
            berak(s1, x, 1, c);
        }
    }
    s1.clear();
    reverse(g[c].begin(), g[c].end());
    for(int x : g[c]){
        if(!volt[x]){
            bejar(s1, s2, x, 1, c, alatt[c] - alatt[x]);
            berak(s1, x, 1, c);
        }
    }

    //cout<<"centroid: "<<c<<'\n';
    for(auto p : s2){
        //cout<<p.first<<' '<<p.second<<'\n';
        ki[p.first] = max(ki[p.first], p.second);
    }

    for(int x : g[c])
        if(!volt[x])
            decomposition(x);
}

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

    int n;
    cin>>n;

    g.resize(n);
    ki.resize(n+1);
    alatt.resize(n);
    volt.assign(n, false);
    for(int i = 0; i < n-1; i++){
        int a, b;
        cin>>a>>b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    decomposition(0);

    /*cout<<"ki: ";
    for(int i = 0; i <= n; i++) cout<<ki[i]<<' ';
    cout<<'\n';*/

    ki[n] = max(ki[n], 1);
    for(int i = n-1; i >= 0; i--){
        ki[i] = max(ki[i], ki[i+1]);
    }

    for(int i = 1; i <= n; i++){
        cout<<(i%2 ? 1 : ki[i])<<'\n';
    }

    return 0;
}

/*
4
1 2
2 3
3 4
*/

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80