oj.uz

Submission #804326

# Submission time Handle Problem Language Result Execution time Memory
804326 2023-08-03T08:02:52 Z vjudge1 Meetings 2 (JOI21_meetings2) C++17
0 / 100
 2 ms 4948 KB 
#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) {
    depth[v] = depth[p] + 1;
    up[ok][v] = p;
    ++ cnt[ok][depth[v]];
    for(auto &u : adj[v]) {
        if(u != p) {
            dfs1(u, v, ok);
        }
    }
}

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);
    
    a = b = ans;

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

Compilation message

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 2 ms 4948 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 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 2 ms 4948 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 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 2 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -