oj.uz

Submission #994383

# Submission time Handle Problem Language Result Execution time Memory
994383 2024-06-07T14:16:47 Z snpmrnhlol Meetings 2 (JOI21_meetings2) C++17
0 / 100
 2 ms 8880 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Incorrect 1 ms 8880 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Incorrect 1 ms 8880 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Incorrect 1 ms 8880 KB Output isn't correct
5 Halted 0 ms 0 KB -