oj.uz

Submission #564221

# Submission time Handle Problem Language Result Execution time Memory
564221 2022-05-18T18:50:37 Z nikatamliani Meetings 2 (JOI21_meetings2) C++14
0 / 100
 5 ms 9816 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, 3>> q;
        for (int j = 1; j <= n; ++j) {
            dist[i][j] = n + 1;
        }
        dist[i][i] = 1;
        for (int to : g[i]) {
            q.push({to, i, to});
        }
        while (!q.empty()) {
            auto [x, p, r] = q.front(); q.pop();
            if (dist[i][x] != n + 1) continue;
            dist[i][x] = dist[i][p] + 1;
            dir[i][x] = r;
            for (int to : g[x]) {
                q.push({to, x, r});
            }
        }
    }
    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]);
        }
    }
    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:42:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |             auto [x, p, r] = q.front(); q.pop();
      |                  ^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Incorrect 5 ms 9816 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Incorrect 5 ms 9816 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Incorrect 5 ms 9816 KB Output isn't correct
6 Halted 0 ms 0 KB -