Submission #1004757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004757		Andrey	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	95 ms	33860 KiB

meetings2

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

vector<int> haha[200001];
vector<int> st(200001);
vector<int> wow[200001];
vector<int> ans(200001,0);
vector<int> dep(200001);

void dfs(int a, int t) {
    st[a] = 1;
    for(int v: haha[a]) {
        if(v != t) {
            dfs(v,a);
            st[a]+=st[v];
        }
    }
}

void dude(int a, int t, int d) {
    st[a] = 1;
    int p = -1,big = 0;
    dep[a] = d;
    for(int v: haha[a]) {
        if(v != t) {
            dude(v,a,d+1);
            st[a]+=st[v];
            if(st[v] > big) {
                big = st[v];
                p = v;
            }
        }
    }
    if(p == -1) {
        wow[a].push_back(d);
    }
    else {
        swap(wow[a],wow[p]);
        for(int v: haha[a]) {
            if(v != t && v != p) {
                for(int j = 0; j < wow[v].size(); j++) {
                    ans[j+1] = max(ans[j+1],wow[v][j]+wow[a][j]-2*d);
                    wow[a][j] = max(wow[a][j],wow[v][j]);
                }
                for(int j = wow[v].size()-2; j >= 0; j--) {
                    wow[v][j] = max(wow[v][j],wow[v][j+1]);
                }
            }
        }
        for(int i = wow[a].size(); i < st[a]; i++) {
            wow[a].push_back(d);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,a,b;
    cin >> n;
    for(int i = 0; i < n-1; i++) {
        cin >> a >> b;
        haha[a].push_back(b);
        haha[b].push_back(a);
    }
    dfs(1,-1);
    int c = 1;
    bool yeah = true;
    while(yeah) {
        yeah = false;
        for(int v: haha[c]) {
            if(st[v] > n/2 && st[v] < st[c]) {
                c = v;
                yeah = true;
                break;
            }
        }
    }
    dude(c,-1,0);
    for(int i = 1; i <= n; i++) {
        if(i != c) {
            ans[st[i]] = max(ans[st[i]],dep[i]);
        }
    }
    for(int i = n-1; i >= 1; i--) {
        ans[i] = max(ans[i],ans[i+1]);
    }
    for(int i = 1; i <= n; i++) {
        if(i%2 == 0) {
            cout << ans[i/2]+1 << "\n";
        }
        else {
            cout << 1 << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

meetings2.cpp: In function 'void dude(int, int, int)':
meetings2.cpp:41:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |                 for(int j = 0; j < wow[v].size(); j++) {
      |                                ~~^~~~~~~~~~~~~~~

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