oj.uz

Submission #893387

# Submission time Handle Problem Language Result Execution time Memory
893387 2023-12-27T04:01:56 Z vjudge1 Meetings 2 (JOI21_meetings2) C++17
20 / 100
 493 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <vector<int>> G(n);
    for ( int i = 1; i < n; i++ ){
        int u, v; cin >> u >> v;
        --u, --v;
        G[u].pb(v), G[v].pb(u);
    }
    vector <vector<int>> s(n, vector <int> (n)), d(n, vector <int> (n));
    for ( int i = 0; i < n; i++ ){
        auto dfs = [&](auto dfs, int u, int p) -> void{
            s[i][u] = 1;
            for ( auto &v: G[u] ){
                if ( v != p ){
                    d[i][v] = d[i][u] + 1;
                    dfs(dfs, v, u);
                    s[i][u] += s[i][v];
                }
            }
        };
        dfs(dfs, i, -1);
    }
    vector <int> sf(n + 1);
    for ( int i = 0; i < n; i++ ){
        for ( int j = i + 1; j < n; j++ ){
            int q = min(s[i][j], s[j][i]) * 2;
            chmax(sf[q], d[i][j] + 1);
        }
    }
    for ( int i = n - 1; i > 0; i-- ){
        chmax(sf[i], sf[i + 1]);
    }
    for ( int i = 2; i <= n; i += 2 ){
        chmax(sf[i], 1);
    }
    for ( int i = 1; i <= n; i++ ){
        cout << (i & 1 ? 1LL : sf[i]) << ln;
    }

    cout << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 460 ms 249596 KB Output is correct
23 Correct 460 ms 249936 KB Output is correct
24 Correct 468 ms 244328 KB Output is correct
25 Correct 456 ms 246560 KB Output is correct
26 Correct 453 ms 245072 KB Output is correct
27 Correct 459 ms 251692 KB Output is correct
28 Correct 465 ms 251552 KB Output is correct
29 Correct 470 ms 251552 KB Output is correct
30 Correct 493 ms 251544 KB Output is correct
31 Correct 466 ms 251472 KB Output is correct
32 Correct 453 ms 251456 KB Output is correct
33 Correct 406 ms 251472 KB Output is correct
34 Correct 407 ms 251264 KB Output is correct
35 Correct 394 ms 251556 KB Output is correct
36 Correct 369 ms 251564 KB Output is correct
37 Correct 360 ms 251732 KB Output is correct
38 Correct 379 ms 251484 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 460 ms 249596 KB Output is correct
23 Correct 460 ms 249936 KB Output is correct
24 Correct 468 ms 244328 KB Output is correct
25 Correct 456 ms 246560 KB Output is correct
26 Correct 453 ms 245072 KB Output is correct
27 Correct 459 ms 251692 KB Output is correct
28 Correct 465 ms 251552 KB Output is correct
29 Correct 470 ms 251552 KB Output is correct
30 Correct 493 ms 251544 KB Output is correct
31 Correct 466 ms 251472 KB Output is correct
32 Correct 453 ms 251456 KB Output is correct
33 Correct 406 ms 251472 KB Output is correct
34 Correct 407 ms 251264 KB Output is correct
35 Correct 394 ms 251556 KB Output is correct
36 Correct 369 ms 251564 KB Output is correct
37 Correct 360 ms 251732 KB Output is correct
38 Correct 379 ms 251484 KB Output is correct
39 Runtime error 166 ms 262144 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -