oj.uz

Submission #907524

# Submission time Handle Problem Language Result Execution time Memory
907524 2024-01-15T19:39:09 Z box Meetings 2 (JOI21_meetings2) C++17
100 / 100
 348 ms 47696 KB 
#include <bits/stdc++.h>
using namespace std;

#ifndef LOCAL
#define cerr if (0) cerr
#endif

typedef vector<int> vi;

const int MAXN = 2e5, MAXL = 18;

int N, sz[MAXN];
vi adj[MAXN], who[MAXN+1];
int depth[MAXN], jmp[MAXN][MAXL];
int ans[MAXN+1];

void make_sz(int p, int i) {
    sz[i] = 1;
    for (int j : adj[i]) if (p != j) {
        make_sz(i, j);
        sz[i] += sz[j];
    }
}

void dfs(int i) {
    for (int l = 1; l < MAXL; l++) jmp[i][l] = jmp[jmp[i][l-1]][l-1];
    sz[i] = 1;
    for (int j : adj[i]) if (jmp[i][0]^j) {
        jmp[j][0] = i;
        depth[j] = depth[i]+1;
        dfs(j);
        sz[i] += sz[j];
    }
    who[sz[i]].push_back(i);
}

int lca(int i, int j) {
    if (depth[i] < depth[j]) swap(i, j);
    int d = depth[i]-depth[j];
    for (int l = 0; l < MAXL; l++) if (d>>l&1) i = jmp[i][l];
    if (i == j) return i;
    for (int l = MAXL-1; l >= 0; l--) if (jmp[i][l]^jmp[j][l]) i = jmp[i][l], j = jmp[j][l];
    return jmp[i][0];
}

int dist(int i, int j) {
    return depth[i]+depth[j]-2*depth[lca(i, j)];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        int x, y; cin >> x >> y, x--, y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int c = [&]() {
        make_sz(-1, 0);
        int i = 0;
        while (1) {
            int c = -1;
            for (int j : adj[i]) if (sz[j] < sz[i] && sz[j]*2 > N) c = j;
            if (c == -1) break;
            i = c;
        }
        return i;
    }();
    cerr << "GOT c=" << c+1 << endl;
    jmp[c][0] = c;
    dfs(c);
    int d = 0, x = c, y = c;
    for (int s = N/2; s >= 1; s--) {
        for (int i : who[s]) {
            int a = dist(x, i), b = dist(y, i);
            if (a < b) swap(a, b), swap(x, y);
            if (a > d) d = a, y = i;
        }
        ans[s*2] = d;
    }
    for (int k = 1; k <= N; k++) cout << ans[k]+1 << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 5 ms 13028 KB Output is correct
6 Correct 5 ms 13020 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 5 ms 13148 KB Output is correct
10 Correct 3 ms 13024 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 4 ms 12892 KB Output is correct
17 Correct 4 ms 12892 KB Output is correct
18 Correct 4 ms 12888 KB Output is correct
19 Correct 3 ms 12888 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12996 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 5 ms 13028 KB Output is correct
6 Correct 5 ms 13020 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 5 ms 13148 KB Output is correct
10 Correct 3 ms 13024 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 4 ms 12892 KB Output is correct
17 Correct 4 ms 12892 KB Output is correct
18 Correct 4 ms 12888 KB Output is correct
19 Correct 3 ms 12888 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12996 KB Output is correct
22 Correct 5 ms 13144 KB Output is correct
23 Correct 6 ms 13148 KB Output is correct
24 Correct 6 ms 13148 KB Output is correct
25 Correct 6 ms 13148 KB Output is correct
26 Correct 6 ms 13148 KB Output is correct
27 Correct 7 ms 13040 KB Output is correct
28 Correct 6 ms 13144 KB Output is correct
29 Correct 7 ms 13148 KB Output is correct
30 Correct 5 ms 13148 KB Output is correct
31 Correct 5 ms 13148 KB Output is correct
32 Correct 6 ms 13404 KB Output is correct
33 Correct 5 ms 13480 KB Output is correct
34 Correct 5 ms 13148 KB Output is correct
35 Correct 6 ms 13148 KB Output is correct
36 Correct 6 ms 13148 KB Output is correct
37 Correct 5 ms 13148 KB Output is correct
38 Correct 6 ms 13148 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 5 ms 13028 KB Output is correct
6 Correct 5 ms 13020 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 5 ms 13148 KB Output is correct
10 Correct 3 ms 13024 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 4 ms 12892 KB Output is correct
17 Correct 4 ms 12892 KB Output is correct
18 Correct 4 ms 12888 KB Output is correct
19 Correct 3 ms 12888 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 12996 KB Output is correct
22 Correct 5 ms 13144 KB Output is correct
23 Correct 6 ms 13148 KB Output is correct
24 Correct 6 ms 13148 KB Output is correct
25 Correct 6 ms 13148 KB Output is correct
26 Correct 6 ms 13148 KB Output is correct
27 Correct 7 ms 13040 KB Output is correct
28 Correct 6 ms 13144 KB Output is correct
29 Correct 7 ms 13148 KB Output is correct
30 Correct 5 ms 13148 KB Output is correct
31 Correct 5 ms 13148 KB Output is correct
32 Correct 6 ms 13404 KB Output is correct
33 Correct 5 ms 13480 KB Output is correct
34 Correct 5 ms 13148 KB Output is correct
35 Correct 6 ms 13148 KB Output is correct
36 Correct 6 ms 13148 KB Output is correct
37 Correct 5 ms 13148 KB Output is correct
38 Correct 6 ms 13148 KB Output is correct
39 Correct 199 ms 36344 KB Output is correct
40 Correct 222 ms 36300 KB Output is correct
41 Correct 203 ms 36444 KB Output is correct
42 Correct 185 ms 36592 KB Output is correct
43 Correct 220 ms 36680 KB Output is correct
44 Correct 196 ms 36568 KB Output is correct
45 Correct 348 ms 43232 KB Output is correct
46 Correct 250 ms 47696 KB Output is correct
47 Correct 208 ms 36980 KB Output is correct
48 Correct 155 ms 37064 KB Output is correct
49 Correct 173 ms 37264 KB Output is correct
50 Correct 165 ms 37216 KB Output is correct
51 Correct 232 ms 45476 KB Output is correct