Submission #427318

#	Time	Username	Problem	Language	Result	Execution time	Memory
427318		Osama_Alkhodairy	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1758 ms	28360 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 200001;

int n, sz[N], blocked[N], tree[2 * N];
vector <int> v[N], ans;
vector <pair <int, int> > c;

void update(int p, int v, int d){
    p += n + 1;
    if(d == 1) tree[p] = v;
    else tree[p] = max(tree[p], v);
    for(; p > 1 ; p >>= 1){
        tree[p >> 1] = max(tree[p], tree[p ^ 1]);
    }
}
int query(int l, int r){
    r++;
    int ret = 0;
    for(l += n + 1, r += n + 1 ; l < r ; l >>= 1, r >>= 1){
        if(l & 1) ret = max(ret, tree[l++]);
        if(r & 1) ret = max(ret, tree[--r]);
    }
    return ret;
}
void dfsz(int node, int pnode){
    sz[node] = 1;
    for(auto &i : v[node]){
        if(i == pnode || blocked[i]) continue;
        dfsz(i, node);
        sz[node] += sz[i];
    }
}
int find(int node, int pnode, int n){
    for(auto &i : v[node]){
        if(i != pnode && !blocked[i] && 2 * sz[i] > n){
            return find(i, node, n);
        }
    }
    return node;
}
void dfs(int node, int pnode, int len){
    c.push_back(make_pair(sz[node], len));
    for(auto &i : v[node]){
        if(i == pnode || blocked[i]) continue;
        dfs(i, node, len + 1);
    }
}
void solve(int node){
    dfsz(node, 0);
    int cen = find(node, 0, sz[node]);
    dfsz(cen, 0);
    for(int itt = 0 ; itt < 2 ; itt++){
        vector <pair <int, int> > all;
        for(auto &i : v[cen]){
            if(blocked[i]) continue;
            c.clear();
            dfs(i, cen, 1);
            for(auto &j : c){
                int mx = query(j.first, n);
                if(mx > 0) ans[j.first] = max(ans[j.first], j.second + mx);
            }
            for(auto &j : c){
                update(j.first, j.second, 0);
                ans[min(j.first, sz[cen] - sz[i])] = max(ans[min(j.first, sz[cen] - sz[i])], j.second);
                all.push_back(j);
            }
        }
        for(auto &i : all){
            update(i.first, 0, 1);
        }
        reverse(v[cen].begin(), v[cen].end());
    }
    blocked[cen] = 1;
    for(auto &i : v[cen]){
        if(blocked[i]) continue;
        solve(i);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0 ; i < n - 1 ; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    ans.resize(n + 1);
    solve(1);
    for(int i = n ; i > 1 ; i--){
        ans[i - 1] = max(ans[i - 1], ans[i]);
    }
    for(int i = 1 ; i <= n ; i++){
        if(i % 2) cout << "1\n";
        else cout << ans[i / 2] + 1 << "\n";
    }
}

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