oj.uz

Submission #991216

# Submission time Handle Problem Language Result Execution time Memory
991216 2024-06-01T15:15:22 Z 12345678 Meetings 2 (JOI21_meetings2) C++17
0 / 100
 13 ms 24152 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5, kx=20;

int n, u, v, sz[nx], dist[nx][kx], c[nx], lvl[nx], used[nx], vs[nx], pa[nx][kx], res[nx], mx, ans[2*nx], lvl2[nx], in[nx], out[nx], t;
vector<int> d[nx], upd, szz[nx], rsz[nx];
multiset<pair<int, int>> ms[nx];
priority_queue<pair<int, int>> pq;

int dfssz(int u, int p)
{
    sz[u]=1;
    for (auto v:d[u]) if (v!=p&&!used[v]) sz[u]+=dfssz(v, u);
    return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto v:d[u]) if (v!=p&&!used[v]&&2*sz[v]>rtsz) return findcentroid(v, u, rtsz);
    return u; 
}

void filldist(int u, int p, int w, int l)
{
    dist[u][l]=w;
    for (auto v:d[u]) if (v!=p&&!used[v]) filldist(v, u, w+1, l);
}

void decomposition(int u, int p)
{
    u=findcentroid(u, u, dfssz(u, u));
    used[u]=1;
    lvl[u]=(p!=-1)?(lvl[p]+1):0;
    c[u]=p;
    filldist(u, u, 0, lvl[u]);
    for (auto v:d[u]) if (v!=p&&!used[v]) decomposition(v, u);
}

void dfs(int u, int p)
{
    in[u]=++t;
    pa[u][0]=p;
    lvl2[u]=lvl2[p]+1;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    sz[u]=1;
    for (auto v:d[u]) if (v!=p) dfs(v, u), sz[u]+=sz[v];
    out[u]=t;
}

int query(int u)
{
    int mxd=0, st=u;
    while (c[u]!=-1)
    {
        if (!ms[c[u]].empty()&&prev(ms[c[u]].end())->second!=u) mxd=max(mxd, dist[st][lvl[c[u]]]+prev(ms[c[u]].end())->first);
        else if (ms[c[u]].size()>=2) mxd=max(mxd, dist[st][lvl[c[u]]]+prev(prev(ms[c[u]].end()))->first);
        u=c[u];
    }
    return mxd;
}

void open(int u)
{
    int st=u;
    while (c[u]!=-1) ms[c[u]].insert({dist[st][lvl[c[u]]], u}), u=c[u];
}

void close(int u)
{
    int st=u;
    while (c[u]!=-1) ms[c[u]].erase(ms[c[u]].find({dist[st][lvl[c[u]]], u})), u=c[u];
}

struct segtree
{
    int d[4*nx];
    void update(int l, int r, int i, int idx, int vl)
    {
        if (r<idx||idx<l) return;
        if (l==r) return d[i]=vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    decomposition(1, -1);
    //for (int i=1; i<=n; i++) cout<<"centroid "<<i<<' '<<c[i]<<'\n';
    dfs(1, 1);
    pq.push({sz[1], 1});
    while (!pq.empty())
    {
        auto [w, u]=pq.top();
        pq.pop();
        open(u);
        if (pa[u][0]!=u&&!vs[pa[u][0]]) close(pa[u][0]), vs[pa[u][0]]=1;
        res[w]=max(res[w], query(u));
        for (auto v:d[u]) if (v!=pa[u][0]) pq.push({sz[v], v});
    }
    for (int i=1; i<=n; i++)
    {
        if (sz[1]-sz[i]<sz[i]) continue;
        int u=i;
        for (int j=kx-1; j>=0; j--) if (sz[1]-sz[pa[u][j]]>=sz[i]) u=pa[u][j];
        res[sz[i]]=max(res[sz[i]], lvl2[i]-lvl2[u]+1);
    }
    for (int i=1; i<=n; i++) szz[sz[i]].push_back(i), rsz[sz[1]-sz[i]].push_back(i);
    for (int i=n; i>=1; i--)
    {
        for (auto u:szz[i]) s.update(1, n, 1, in[u], lvl2[u]);
        for (auto u:rsz[i]) res[i]=max(res[i], s.query(1, n, 1, in[u], out[u])-lvl2[u]+1);
    }
    for (int i=n; i>=1; i--) res[i]=max(res[i], res[i+1]);
    for (int i=1; i<=n; i++) ans[i]=1;
    for (int i=1; i<=n; i++) ans[2*i]=max(ans[2*i], res[i]+1);
    for (int i=1; i<=n; i++) cout<<ans[i]<<'\n';
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23904 KB Output is correct
2 Correct 9 ms 24032 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 9 ms 23964 KB Output is correct
5 Correct 10 ms 23908 KB Output is correct
6 Correct 9 ms 23992 KB Output is correct
7 Correct 9 ms 23904 KB Output is correct
8 Correct 9 ms 23884 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 9 ms 23912 KB Output is correct
11 Incorrect 10 ms 23904 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23904 KB Output is correct
2 Correct 9 ms 24032 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 9 ms 23964 KB Output is correct
5 Correct 10 ms 23908 KB Output is correct
6 Correct 9 ms 23992 KB Output is correct
7 Correct 9 ms 23904 KB Output is correct
8 Correct 9 ms 23884 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 9 ms 23912 KB Output is correct
11 Incorrect 10 ms 23904 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23904 KB Output is correct
2 Correct 9 ms 24032 KB Output is correct
3 Correct 13 ms 24152 KB Output is correct
4 Correct 9 ms 23964 KB Output is correct
5 Correct 10 ms 23908 KB Output is correct
6 Correct 9 ms 23992 KB Output is correct
7 Correct 9 ms 23904 KB Output is correct
8 Correct 9 ms 23884 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 9 ms 23912 KB Output is correct
11 Incorrect 10 ms 23904 KB Output isn't correct
12 Halted 0 ms 0 KB -