Submission #994383

#	Time	Username	Problem	Language	Result	Execution time	Memory
994383		snpmrnhlol	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	2 ms	8880 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int inf = 2e9;
vector <int> e[N];
int bad[N];
int sub[N];
int gbsub[N];
int pr[N];
int ans[N + 1];
int n;
void dfs(int node, int p){
    gbsub[node] = 1;
    pr[node] = p;
    for(auto i:e[node]){
        if(i == p)continue;
        dfs(i,node);
        gbsub[node]+=gbsub[i];
    }
}
int get(int node, int p){
    if(pr[node] == p){
        return gbsub[node];
    }else{
        return n - gbsub[p];
    }
}
void cendecomp(int node){
    vector <array<int,3>> nodes;
    int sz = 0;
    int cen = -1,cennr = inf;
    auto dfs = [&](auto self, int node, int p) -> void{
        sz++;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
        }
    };
    auto dfs2 = [&](auto self, int node, int p) -> void{
        sub[node] = 1;
        int mx = -1;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
            sub[node]+=sub[i];
            mx = max(mx,sub[i]);
        }
        mx = max(mx,sz - sub[node]);
        if(mx < cennr){
            mx = cennr;
            cen = node;
        }
    };
    auto dfs3 = [&](auto self, int node, int p, int dpth, int orig) -> void{
        int nr = min(get(node,p),get(cen,orig));
        ans[2*nr] = max(dpth,ans[2*nr]);
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node, dpth + 1, orig);
        }
    };
    auto dfs4 = [&](auto self, int node, int p, int dpth, int orig) -> void{
        nodes.push_back({orig,dpth,get(node,p)});
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node, dpth + 1, orig);
        }
    };
    dfs(dfs, node, -1);
    dfs2(dfs2, node, -1);
    for(auto i:e[cen]){
        if(bad[i])continue;
        dfs3(dfs3, i, cen, 2, i);
        dfs4(dfs4, i, cen, 1, i);
    }
    for(int i = 0;i < nodes.size();i++){
        for(int j = 0;j < nodes.size();j++){
            if(nodes[i][0] == nodes[j][0])continue;
            ans[min(nodes[i][2],nodes[j][2])] = max(ans[min(nodes[i][2],nodes[j][2])],nodes[i][1] + nodes[j][1]);
        }
    }
    bad[cen] = 1;
    for(auto i:e[cen]){
        if(bad[i])continue;
        cendecomp(i);
    }
}
void solve(){
    cin>>n;
    for(int i = 0;i < n - 1;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        e[w].push_back(u);
        e[u].push_back(w);
    }
    dfs(0, -1);
    cendecomp(0);
    for(int i = 1;i <= n;i++){
        if(i%2 == 1)cout<<1<<'\n';
        else cout<<ans[i]<<'\n';
    }
}
int main(){
    int t;
    t = 1;
    while(t--)solve();
    return 0;
}

Compilation message (stderr)

meetings2.cpp: In function 'void cendecomp(int)':
meetings2.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0;i < nodes.size();i++){
      |                   ~~^~~~~~~~~~~~~~
meetings2.cpp:77:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int j = 0;j < nodes.size();j++){
      |                       ~~^~~~~~~~~~~~~~

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