Submission #1028706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028706		underwaterkillerwhale	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	513 ms	25676 KiB

meetings2

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 320;
const int INF = 1e9;
const int BASE = 1337;

int n;
vector<int> ke[N];


namespace sub5 {
    inline void maximize (int &a, int b) { if (a < b) a = b; }

    int m;

    int a[N];
    int Ans[N];

    bool del[N];
    int nChild[N];

    int sufmx[N];

    void pdfs (int u, int p) {
        nChild[u] = 1;
        iter (&v, ke[u]) {
            if (v != p && !del[v]) {
                pdfs (v, u);
                nChild[u] += nChild[v];
            }
        }
    }

    int get_cen (int u, int p, int tot) {
        iter (&v, ke[u]) {
            if (v != p && !del[v] && nChild[v] >= tot / 2)
                return get_cen(v, u, tot);
        }
        return u;
    }

    void dfs (int u, int p, int typ, int Dist = 1) {
        if (typ == 1) maximize(sufmx[nChild[u]], Dist);
        else {
            maximize (Ans[nChild[u]], Dist + sufmx[nChild[u]] + 1);
        }
        iter (&v, ke[u]) {
            if (v != p && !del[v]) {
                dfs (v, u, typ, Dist + 1);
            }
        }
    }

    void calc_cen (int u, int p, int delta, int Dist = 0) {
        if (nChild[u] <= delta)
            maximize(Ans[nChild[u]], Dist + 1);
        iter (&v, ke[u]) if (!del[v] && v != p) calc_cen(v, u, delta, Dist + 1);
    }

    void Clear (int mxC) {
        rep (i, 1, mxC + 1) sufmx[i] = -INF;
    }

    void cen_dcps (int root) {
        pdfs (root, 0);
        int cen = get_cen (root, 0, nChild[root]);
        int mxC = 0;
        pdfs (cen, 0);
        iter (&v, ke[cen]) {
            if (!del[v]) {
                maximize(mxC, nChild[v]);
                dfs (v, cen, 0);
                dfs (v, cen, 1);
                reb (i, nChild[v], 1) maximize(sufmx[i], sufmx[i + 1]);
            }
        }
        Clear(mxC);
        reb (i, SZ(ke[cen]) - 1, 0) {
            int v = ke[cen][i];
            if (!del[v]) {
                dfs (v, cen, 0);
                dfs (v, cen, 1);
                reb (i, nChild[v], 1) maximize(sufmx[i], sufmx[i + 1]);
            }
        }
        Clear(mxC);
        iter (&v, ke[cen]) {
            if (!del[v]) {
                dfs (v, cen, 1);
                int delta = nChild[cen] - nChild[v];
                reb (i, nChild[v], 1) maximize (sufmx[i], sufmx[i + 1]);
                maximize(Ans[delta], sufmx[delta]);
                calc_cen (v, cen, delta);
                Clear(nChild[v]);
            }
        }
        del[cen] = 1;
        iter (&v, ke[cen]) {
            if (!del[v]) {
                cen_dcps(v);
            }
        }
    }

    void solution() {
        rep (i, 1, n + 1) Ans[i] = 1;
        cen_dcps(1);
        reb (i, n, 1) maximize(Ans[i], Ans[i + 1]);
        rep (i, 1, n) {
            if (i & 1) {
                cout << 1 <<"\n";
            }
            else {
                cout << Ans[i / 2] <<"\n";
            }
        }
    }
}

namespace sub1 {
    const ll N1 = 20;
    int Dist[N1][N1];
    void dfs (int root, int u, int p, int Dst = 0) {
        Dist[root][u] = Dst;
        iter (&v, ke[u]) {
            if (v != p) {
                dfs (root, v, u, Dst + 1);
            }
        }
    }
    void solution () {
        rep (i, 1, n) dfs (i, i, 0);
        rep (k, 1, n) {
            int res = 0;
            rep (msk, 1, (1 << n) - 1) {
                if (__builtin_popcount(msk) != k) continue;
                vector<int> vec;
                rep (i, 1, n) if (bit(msk, i - 1)) vec.push_back(i);
                int mnvl = INF, de = 0;
                rep (i, 1, n) {
                    int cur = 0;
                    iter (&id, vec) cur += Dist[id][i];
                    if (cur < mnvl) {
                        de = 1;
                        mnvl = cur;
                    }
                    else if (cur == mnvl) ++de;
                }
                res = max(res, de);
            }
            cout << res<<"\n";
        }
    }
}

void solution () {
    cin >> n;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    if (n <= 16) sub1 :: solution();
    else
        sub5 :: solution();

}
#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
nếu mình nghĩ sẽ thay đổi định nghĩa, kiểu dữ liệu của hàm hay mảng j thì mình phải nghĩ xem nó sẽ ảnh hưởng đến các phần nào
5 10
798981764 -961045489
-762214604 -6816243
549909709 362471127
504233152 -881315415
503023672 -79630788
*/

Compilation message (stderr)

meetings2.cpp: In function 'void sub1::solution()':
meetings2.cpp:157:46: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  157 |                 rep (i, 1, n) if (bit(msk, i - 1)) vec.push_back(i);
      |                                            ~~^~~
meetings2.cpp:11:34: note: in definition of macro 'bit'
   11 | #define bit(msk, i)     ((msk >> i) & 1)
      |                                  ^

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