Submission #1008385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008385		Unforgettablepl	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	4033 ms	23036 KiB

meetings2

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

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> adj(n+1);
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    int centroid = -1;
    function<int(int,int)> find_centroid = [&](int x,int p){
        int siz = 1;
        for(int&i:adj[x])if(i!=p)siz+=find_centroid(i,x);
        if(n-siz<=n/2 and siz<=n){
            centroid = x;
            return (int)1e15;
        }
        return siz;
    };
    find_centroid(1,0);
    vector<int> depths;
    vector<int> subsize;
    function<int(int,int,int)> dfs = [&](int x,int p,int depth){
        int siz = 1;
        vector<int> idx = {(int)depths.size()};
        depths.emplace_back(depth);
        subsize.emplace_back(0);
        for(int&i:adj[x])if(i!=p){
            siz+=dfs(i,x,depth+1);
            idx.emplace_back(depths.size());
            depths.emplace_back(depth);
            subsize.emplace_back(0);
        }
        for(int&i:idx)subsize[i]=siz;
        return siz;
    };
    dfs(centroid,0,1);
    vector<int> ans(n+1);
    for(int i=0;i<depths.size();i++){
        int mindep = depths[i];
        for(int j=i+1;j<depths.size();j++){
            mindep = min(mindep,depths[j]);
            ans[min(subsize[i],subsize[j])]=max(ans[min(subsize[i],subsize[j])],depths[i]+depths[j]-2ll*mindep+1ll);
        }
    }
    for(int i=n-1;i;i--)ans[i]=max(ans[i],ans[i+1]);
    for(int i=1;i<=n;i++){
        if(i&1)cout<<"1\n";
        else cout<<ans[i/2]<<'\n';
    }
}

Compilation message (stderr)

meetings2.cpp: In function 'int32_t main()':
meetings2.cpp:47:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<depths.size();i++){
      |                 ~^~~~~~~~~~~~~~
meetings2.cpp:49:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j=i+1;j<depths.size();j++){
      |                       ~^~~~~~~~~~~~~~

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