Submission #1307734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307734		oloc	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	271 ms	110352 KiB

meetings2

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vect;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define pb push_back
#define f first
#define s second

const int N = 2e5 + 5;

vect graf[N], kol, lg;
vector<vector<pii>> st;

int n;
int gl[N], pre[N], podd[N], ojc[N];
pii sr[N];

void dfs_prep(int v, int p){
    pre[v] = kol.size();
    kol.pb(v);
    podd[v] = 1;

    for(int u : graf[v]){
        if(u == p) continue;
        gl[u] = gl[v] + 1;
        dfs_prep(u, v);
        podd[v] += podd[u];
        kol.pb(v);
    }
}


void build(int n){
    lg.assign(n + 1, 0);
    for(int i = 2; i <= n; i++){
        lg[i] = lg[i / 2] + 1;
    }

    int logi = lg[n] + 1;
    st.assign(n, vector<pii>(logi));

    for(int i = 0; i < n; i++){
        st[i][0] = {gl[kol[i]], kol[i]};
    }

    for(int j = 1; j < logi; j++){
        for(int i = 0; i + (1 << j) <= n; i++){
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r){
    int dl = r - l + 1;
    int logi = lg[dl];
    return min(st[l][logi], st[r - (1 << logi) + 1][logi]).s;
}

int lca(int x, int y){
    if(pre[x] > pre[y]) swap(x, y);
    return query(pre[x], pre[y]);
}

int odl(int x, int y){
    return gl[x] + gl[y] - 2 * gl[lca(x, y)];
}


int Find(int x){
    if(ojc[x] != x)
        ojc[x] = Find(ojc[x]);
    return ojc[x];
}

void unionek(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x == y) return;

    vector<int> kand;
    kand.pb(sr[x].f);
    kand.pb(sr[x].s);
    kand.pb(sr[y].f);
    kand.pb(sr[y].s);

    int best = 0;
    pii akt = sr[x];

    for(int i = 0; i < 4; i++){
        for(int j = i + 1; j < 4; j++){
            int d = odl(kand[i], kand[j]);
            if(d > best){
                best = d;
                akt = {kand[i], kand[j]};
            }
        }
    }

    ojc[y] = x;
    sr[x] = akt;
}

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

    cin >> n;

    for(int i = 1; i <= n; i++){
        ojc[i] = i;
        sr[i] = {i, i};
    }

    vector<pii> kraw;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].pb(b);
        graf[b].pb(a);
        kraw.pb({a, b});
    }

    kol.clear();
    gl[1] = 0;
    dfs_prep(1, 0);
    build(kol.size());

    vector<vector<pii>> order(n / 2 + 1);

    for(auto x : kraw){
        int a = x.f, b = x.s, syn;
        if(podd[a] < podd[b]){
        	syn = a;
        }else{
        	syn = b;
        }
        int roz = min(podd[syn], n - podd[syn]);
        if(roz >= 1 && roz <= n / 2){
        	order[roz].pb(x);
        }
    }

    vector<int> wyn(n + 1, 1);
    int best = 0;

    for(int i = n / 2; i >= 1; i--){
        for(auto x : order[i]){
        	int a = x.f, b = x.s;
            unionek(a, b);
            a = Find(a);
            best = max(best, odl(sr[a].f, sr[a].s));
        }
        wyn[2 * i] = best + 1;
    }

    for(int i = 1; i <= n; i++){
    	cout << wyn[i] << "\n";
    }


    return 0;
}

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