Submission #536936

#	Time	Username	Problem	Language	Result	Execution time	Memory
536936		someone	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	399 ms	38692 KiB

meetings2

#include <bits/stdc++.h>
//#define int long long
using namespace std;

struct Val {
    int val, i;
};

const int N = 2e5 + 42, T = 18, INF = 1e18;

Val val[N];
vector<int> adj[N];
int n, root, id = 0, sz[N], ans[N], dist[N], deb[N], fin[N], bl[T][N];

int DFS(int i, int pre) {
    int maxi = 0, sum = 1;
    for(int j : adj[i])
        if(j != pre) {
            int val = DFS(j, i);
            sum += val;
            maxi = max(maxi, val);
        }
    maxi = max(maxi, n - sum);
    if(maxi <= n/2)
        root = i;
    return sum;
}

int getSz(int i, int pre) {
    sz[i] = 1;
    deb[i] = id++;
    bl[0][i] = pre;
    dist[i] = dist[pre] + 1;
    for(int j : adj[i])
        if(j != pre)
            sz[i] += getSz(j, i);
    fin[i] = id++;
    return sz[i];
}

inline bool ancester(int a, int b) {
    return deb[a] <= deb[b] && fin[b] <= fin[a];
}

int LCA(int a, int b) {
    if(dist[a] < dist[b])
        swap(a, b);
    if(ancester(b, a))
        return b;
    for(int i = T-1; i > -1; i--)
        while(!ancester(bl[i][a], b)) {
            a = bl[i][a];
            if(dist[a] < dist[b])
                swap(a, b);
        }
    return bl[0][a];
}

inline int distance(int a, int b) {
    return dist[a] + dist[b] - 2 * dist[LCA(a, b)];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    DFS(0, 0);
    getSz(root, root);
    
    for(int i = 0; i < n; i++) {
        val[i].i = i;
        val[i].val = sz[i];
    }
    sort(val, val + n,
    [](Val a, Val b) {
        return a.val > b.val;
    });
    
    for(int i = 1; i < T; i++)
        for(int j = 0; j < n; j++)
            bl[i][j] = bl[i-1][bl[i-1][j]];
    
    int diam1 = root, diam2 = root;
    for(int i = 1; i < n; i++) {
        int dist1 = ans[val[i-1].val],
            dist2 = distance(diam1, val[i].i),
            dist3 = distance(val[i].i, diam2);
        ans[val[i].val] = max(max(dist1, dist2), dist3);
        if(dist2 == ans[val[i].val])
            diam2 = val[i].i;
        else if(dist3 == ans[val[i].val])
            diam1 = val[i].i;
    }
    for(int i = N-2; i > -1; i--)
        ans[i] = max(ans[i], ans[i+1]);
    for(int i = 1; i <= n; i++)
        if(i % 2 == 1)
            cout << "1\n";
        else
            cout << ans[i/2] + 1 << '\n';
}

Compilation message (stderr)

meetings2.cpp:9:39: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 | const int N = 2e5 + 42, T = 18, INF = 1e18;
      |                                       ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80