oj.uz

Submission #804198

# Submission time Handle Problem Language Result Execution time Memory
804198 2023-08-03T07:31:21 Z vjudge1 Meetings 2 (JOI21_meetings2) C++17
0 / 100
 3 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) {
    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

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 3 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 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 80.0

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