Submission #564221

#	Time	Username	Problem	Language	Result	Execution time	Memory
564221		nikatamliani	Meetings 2 (JOI21_meetings2)	C++14	0 / 100	5 ms	9816 KiB

meetings2

#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 (stderr)

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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80