Submission #804198

#	Time	Username	Problem	Language	Result	Execution time	Memory
804198		vjudge1	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	3 ms	4948 KiB

meetings2

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 200200;   

vector < int > adj[N];
int depth[N], mx_depth, a, b, ans, up[2][N], cnt[2][N];

void dfs(int v, int p) {
    depth[v] = depth[p] + 1;    
    for(auto &u : adj[v]) {
        if(u != p) {
            dfs(u, v);
        }
    }
    if(depth[mx_depth] < depth[v]) {
        mx_depth = v;
    }
}

void dfs1(int v, int p, int ok) {
    up[ok][v] = p;
    cnt[ok][v] = 1;
    for(auto &u : adj[v]) {
        if(u != p) {
            dfs1(u, v, ok);
            cnt[ok][v] += cnt[ok][u];
        }
    }
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    for(int u, v, t = n; 0 <-- t;) {
        cin >> u >> v;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    dfs(1, 0);
    a = mx_depth;
    mx_depth = 0;
    dfs(a, 0);
    b = mx_depth;
    ans = depth[b];
   
    dfs1(a, 0, 0);
    dfs1(b, 0, 1);
    
    for(int i = 1; i <= n; ++ i) {
        if(i&1) {
            cout << "1\n";
        } else {
            if(cnt[1][a] < i / 2) {
                a = up[1][a];
                -- ans;
            }
            if(cnt[0][b] < i / 2) {
                b = up[0][b];
                -- ans;
            }
            cout << ans << '\n'; 
        }
    }
} 

Compilation message (stderr)

meetings2.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~

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