oj.uz

Submission #602897

# Submission time Handle Problem Language Result Execution time Memory
602897 2022-07-23T12:30:02 Z AA_Surely Meetings 2 (JOI21_meetings2) C++17
0 / 100
 4 ms 5032 KB 
#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<int, PII> PPI;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 2e5 + 7;
const int INF = 1e9 + 7;

int n;
int sz[N], tmp[N], best[N], ans[N];
bool vis[N];
VI adj[N];

void init() {
    cin >> n;
    F0R(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[--u].PB(--v);
        adj[v].PB(u);
    }

    return;
}

int getSz(int now, int p = -1) {
    sz[now] = 1;
    for(int on : adj[now]) if (!vis[on] && on != p) sz[now] += getSz(on, now);
    return sz[now];
}

int getCent(int now, int p, int nn) {
    for(int on : adj[now]) 
        if (on != p && !vis[on] && sz[on] > nn / 2) 
            return getCent(on, now, nn);
    return now;
}

void dfs(int now, int p, int h) {
    tmp[ sz[now] ] = max(tmp[ sz[now] ], h);
    for(int on : adj[now]) if (!vis[on] && on != p) dfs(on, now, h + 1);
    return;
}

void solve(int now) {
    getSz(now);
    int c = getCent(now, -1, sz[now]);
    /*F0R(i, n) cout << sz[i] << ' '; cout << endl;
    cout << "centroid is " << c + 1 << endl;*/
    getSz(c);

    vis[c] = 1;
    fill(best, best + sz[c] + 1, -INF);
    for(int on : adj[c]) if (!vis[on]) {
        fill(tmp, tmp + sz[on] + 1, 0);
        dfs(on, c, 1);
        R0F(i, sz[on] + 1) tmp[i] = max(tmp[i], tmp[i + 1]);
        FOR(i, 1, sz[on] + 1) {
            ans[i] = max(ans[i], best[i] + tmp[i] + 1);
            best[i] = max(best[i], tmp[i]);

            if (sz[c] - sz[on] >= i) ans[i] = max(ans[i], tmp[i] + 1);
        }
    }

    //cout << "ans until now "; FOR(i, 1, n + 1) cout << (i & 1 ? 1 : ans[i >> 1]) << ' '; cout << endl;

    for(int on : adj[c]) if (!vis[on]) solve(on);
    return;
}

int main() {
    IOS;

    init();
    solve(0);
    FOR(i, 1, n + 1) cout << (i & 1 ? 1 : ans[i >> 1]) << ' ';
    return 0;
}

Subtask #1
0 / 4.0

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