oj.uz

Submission #564223

# Submission time Handle Problem Language Result Execution time Memory
564223 2022-05-18T19:18:12 Z nikatamliani Meetings 2 (JOI21_meetings2) C++14
20 / 100
 834 ms 166784 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> g[N], subs[N];
int n, c, sub[N], done[N], f[N], ans[N], par[N], exc[N];
int excSize(int x, int dir) {
    if (par[x] == dir) {
        return exc[x];
    }
    return n - exc[dir]; 
}
void find_par(int x, int p) {
    par[x] = p;
    exc[x] = 1;
    for (int to : g[x]) {
        if (to != p) {
            find_par(to, x);
            exc[x] += exc[to];
        }
    }
}
int dist[5005][5005], dir[5005][5005];
int main() {
    cin >> n;
    if (n > 5000) return 0;
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    find_par(1, 0);
    for (int i = 1; i <= n; ++i) {
        queue<array<int, 2>> q;
        for (int j = 1; j <= n; ++j) {
            dist[i][j] = n + 1;
        }
        q.push({i, 0});
        while (!q.empty()) {
            auto [x, p] = q.front(); q.pop();
            if (dist[i][x] != n + 1) continue;
            dist[i][x] = dist[i][p] + 1;
            dir[x][i] = p;
            for (int to : g[x]) {
                q.push({to, x});
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            int A = dir[i][j], B = dir[j][i];
            int s1 = excSize(i, A), s2 = excSize(j, B);
            int v = min(s1, s2);
            ans[v] = max(ans[v], dist[i][j]);
        }
    }
    ans[n + 1] = 1;
    for (int i = n; i >= 1; --i) {
        ans[i] = max(ans[i], ans[i + 1]);
    }
    for (int i = 1; i <= n; ++i) {
        if (i % 2 == 0) {
            cout << ans[i / 2] << '\n';
        } else {
            cout << "1\n";
        }
    }
}

Compilation message

meetings2.cpp: In function 'int main()':
meetings2.cpp:39:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |             auto [x, p] = q.front(); q.pop();
      |                  ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 5 ms 9836 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 5 ms 9776 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 7 ms 9888 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 5 ms 9828 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 5 ms 9812 KB Output is correct
16 Correct 5 ms 9828 KB Output is correct
17 Correct 6 ms 9856 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 5 ms 9832 KB Output is correct
20 Correct 5 ms 9812 KB Output is correct
21 Correct 5 ms 9812 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 5 ms 9836 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 5 ms 9776 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 7 ms 9888 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 5 ms 9828 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 5 ms 9812 KB Output is correct
16 Correct 5 ms 9828 KB Output is correct
17 Correct 6 ms 9856 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 5 ms 9832 KB Output is correct
20 Correct 5 ms 9812 KB Output is correct
21 Correct 5 ms 9812 KB Output is correct
22 Correct 711 ms 166160 KB Output is correct
23 Correct 644 ms 166084 KB Output is correct
24 Correct 654 ms 163184 KB Output is correct
25 Correct 708 ms 164384 KB Output is correct
26 Correct 664 ms 163536 KB Output is correct
27 Correct 691 ms 166620 KB Output is correct
28 Correct 741 ms 166744 KB Output is correct
29 Correct 746 ms 166584 KB Output is correct
30 Correct 787 ms 166652 KB Output is correct
31 Correct 736 ms 166540 KB Output is correct
32 Correct 751 ms 166608 KB Output is correct
33 Correct 834 ms 166704 KB Output is correct
34 Correct 673 ms 166632 KB Output is correct
35 Correct 575 ms 166620 KB Output is correct
36 Correct 562 ms 166604 KB Output is correct
37 Correct 580 ms 166628 KB Output is correct
38 Correct 665 ms 166784 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 5 ms 9836 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 5 ms 9776 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 7 ms 9888 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 5 ms 9828 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 5 ms 9812 KB Output is correct
16 Correct 5 ms 9828 KB Output is correct
17 Correct 6 ms 9856 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 5 ms 9832 KB Output is correct
20 Correct 5 ms 9812 KB Output is correct
21 Correct 5 ms 9812 KB Output is correct
22 Correct 711 ms 166160 KB Output is correct
23 Correct 644 ms 166084 KB Output is correct
24 Correct 654 ms 163184 KB Output is correct
25 Correct 708 ms 164384 KB Output is correct
26 Correct 664 ms 163536 KB Output is correct
27 Correct 691 ms 166620 KB Output is correct
28 Correct 741 ms 166744 KB Output is correct
29 Correct 746 ms 166584 KB Output is correct
30 Correct 787 ms 166652 KB Output is correct
31 Correct 736 ms 166540 KB Output is correct
32 Correct 751 ms 166608 KB Output is correct
33 Correct 834 ms 166704 KB Output is correct
34 Correct 673 ms 166632 KB Output is correct
35 Correct 575 ms 166620 KB Output is correct
36 Correct 562 ms 166604 KB Output is correct
37 Correct 580 ms 166628 KB Output is correct
38 Correct 665 ms 166784 KB Output is correct
39 Incorrect 6 ms 9684 KB Output isn't correct
40 Halted 0 ms 0 KB -