Submission #386556

#	Time	Username	Problem	Language	Result	Execution time	Memory
386556		PurpleCrayon	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	695 ms	44996 KiB

meetings2

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

#define ar array
#define sz(v) int(v.size())
const int MAXN = 2e5+10, MAXL = 18, INF = 1e9+10;

int n, depth[MAXN], anc[MAXN][MAXL], st[MAXN], en[MAXN], tt=0;
vector<int> adj[MAXN];

//start lca
void init_lca(int c=0, int p=-1, int d=0){
	depth[c]=d, anc[c][0]=p;
    st[c] = tt++;
	for (int i=1; i < MAXL; i++) anc[c][i] = (anc[c][i-1]==-1?-1:anc[anc[c][i-1]][i-1]);
	for (auto nxt : adj[c]) if (nxt != p) init_lca(nxt, c, d+1);
    en[c] = tt-1;
}
int jmp(int a, int h){
	for (int i = 0; i < MAXL; i++) if ((h>>i)&1) a = anc[a][i];
	return a;
}
int lca(int a, int b){
	if (depth[a] < depth[b]) swap(a, b);
	a = jmp(a, depth[a]-depth[b]);
	if (a==b) return a;
	for (int i = MAXL-1; i >= 0; i--){
		if (anc[a][i] != anc[b][i]) a = anc[a][i], b = anc[b][i];
	}
	assert(anc[a][0]==anc[b][0]);
	return anc[a][0];
}
int dist(int a, int b){ return depth[a]+depth[b]-2*depth[lca(a, b)]; }
//end lca

int sub[MAXN], ans[MAXN];

int dfs1(int c=0, int p=-1){
    sub[c] = 1;
    for (auto nxt : adj[c]) if (nxt != p) sub[c] += dfs1(nxt, c);
    return sub[c];
}

struct pt_upd {
    int n, t[4*MAXN];
    void init(int _n){ n=_n; memset(t, -1, sizeof(t)); }
    void upd(int v, int tl, int tr, int pos, int nv){
        if (pos < tl || pos > tr) return;
        if (tl == tr) {
            t[v] = nv;
            return;
        }
        int tm=(tl+tr)/2;
        upd(2*v, tl, tm, pos, nv), upd(2*v+1, tm+1, tr, pos, nv);
        t[v] = max(t[2*v], t[2*v+1]);
    }
    void upd(int pos, int nv){ upd(1, 0, n-1, pos, nv); }
    int qry(int v, int tl, int tr, int l, int r) {
        if (r < tl || l > tr) return -1;
        if (l <= tl && tr <= r) return t[v];
        int tm=(tl+tr)/2;
        return max(qry(2*v, tl, tm, l, r), qry(2*v+1, tm+1, tr, l, r));
    }
    int qry(int l, int r){ return qry(1, 0, n-1, l, r); }
} seg1;
struct rng_upd {
    int n, t[4*MAXN];
    void init(int _n){ n=_n; fill(t, t+4*n, INF); }
    void upd(int v, int tl, int tr, int l, int r, int val){
        if (r < tl || l > tr) return;
        if (l <= tl && tr <= r) {
            t[v] = min(t[v], val);
            return;
        }
        int tm=(tl+tr)/2;
        upd(2*v, tl, tm, l, r, val), upd(2*v+1, tm+1, tr, l, r, val);
    }
    void upd(int l, int r, int nv){ upd(1, 0, n-1, l, r, nv); }
    int qry(int v, int tl, int tr, int pos) {
        if (tl == tr) return t[v];
        int ans=t[v], tm = (tl+tr)/2;
        if (pos <= tm)
            ans = min(ans, qry(2*v, tl, tm, pos));
        else
            ans = min(ans, qry(2*v+1, tm+1, tr, pos));
        return ans;
    }
    int qry(int pos){ return qry(1, 0, n-1, pos); }
} seg2;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b, --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }
    init_lca();
    dfs1();

    vector<int> p1(n); iota(p1.begin(), p1.end(), 0);
    sort(p1.begin(), p1.end(), [&](int i, int j){ return sub[i] < sub[j]; });

    vector<bool> is_lf(n);
    ar<int, 2> diam{-1, -1};

    vector<int> p2(n-1); iota(p2.begin(), p2.end(), 1);
    sort(p2.begin(), p2.end(), [&](int i, int j){ return n-sub[i] < n-sub[j]; });
    seg1.init(n); seg2.init(n);
    int up_len = -1;

    vector<int> lf;

    int ptr1=n-1, ptr2=n-2;
    for (int i = n; i >= 1; i--) {
        if (i&1){ ans[i] = 1; continue; }
        int v=i/2;
        while (ptr1>=0&&sub[p1[ptr1]]>=v) {
            int j = p1[ptr1];
            
            //cerr << "add down " << j << " for answer " << i << endl;

            if (sz(lf)<=2) {
                if (j){
                    if (is_lf[anc[j][0]]) {
                        lf.erase(find(lf.begin(), lf.end(), anc[j][0]));
                        is_lf[anc[j][0]] = 0;
                    }
                    is_lf[j] = 1;
                    lf.push_back(j);
                }
            }
            if (sz(lf) == 2) {
                diam = {lf[0], lf[1]};
            } else if (sz(lf) > 2) {
                int d1=dist(diam[0], diam[1]), d2=dist(diam[0], j), d3=dist(diam[1], j);
                if (d1 == max({d1, d2, d3})) {
                } else if (d2 == max({d1, d2, d3})) {
                    diam = {diam[0], j};
                } else if (d3 == max({d1, d2, d3})) {
                    diam = {diam[1], j};
                } else assert(false);
            }
            seg1.upd(st[j], depth[j]);
            up_len = max(up_len, depth[j]-seg2.qry(st[j])); 

            ptr1--;
        }
        while (ptr2>=0&&n-sub[p2[ptr2]]>=v) {
            int j = p2[ptr2];
            //cerr << "add up " << j << " for answer " << i << endl;
            
            up_len = max(up_len, seg1.qry(st[j], en[j])-(depth[j]-1));
            seg2.upd(st[j], en[j], (depth[j]-1));

            ptr2--;
        }
        //cerr << "diam: " << i << ' ' << diam[0] << ' ' << diam[1] << ' ' << sz(lf) << endl;

        ans[i] = 1+up_len;
        if (sz(lf) >= 2) ans[i] = max(ans[i], 1+dist(diam[0], diam[1]));
        ans[i] = max(ans[i], 1);
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
}

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