Submission #1028595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028595		underwaterkillerwhale	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	2414 ms	31312 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];

    struct Segment_Tree {
        int m;
        int st[N << 2];

        void init (int n) {
            m = n;
            rep (i, 1, m << 2) st[i] = -INF;
        }
        void update (int id, int l, int r, int pos, int val) {
            if (l > pos || r < pos) return;
            if (l == r) {
                if (val == -INF) st[id] = val;
                else st[id] = max(st[id], val);
                return;
            }
            int mid = l + r >> 1;
            update (id << 1, l, mid, pos, val);
            update (id << 1 | 1, mid + 1, r, pos, val);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }
        int get (int id, int l, int r, int u, int v) {
            if (l > v || r < u) return -INF;
            if (l >= u && r <= v)
                return st[id];
            int mid = l + r >> 1;
            return max(get (id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
        }

        void update (int pos, int val) {
            update (1, 1, m, pos, val);
        }
        int get (int u, int v) {
            return get (1, 1, m, u, v);
        }
    }ST;

    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) ST.update (nChild[u], Dist);
        else if(typ == 3) ST.update (nChild[u], -INF);
        else {
            maximize (Ans[nChild[u]], Dist + ST.get(nChild[u], n) + 1);
        }
        iter (&v, ke[u]) {
            if (v != p && !del[v]) {
                dfs (v, u, typ, Dist + 1);
            }
        }
    }

    void Clear (int u) {
        iter (&v, ke[u]) if (!del[v]) dfs (v, u, 3);
    }

    void cen_dcps (int root) {
        pdfs (root, 0);
        int cen = get_cen (root, 0, nChild[root]);
        pdfs (cen, 0);
        iter (&v, ke[cen]) {
            if (!del[v]) {
                dfs (v, cen, 0);
                dfs (v, cen, 1);
            }
        }
        Clear(cen);
        reb (i, SZ(ke[cen]) - 1, 0) {
            int v = ke[cen][i];
            if (!del[v]) {
                dfs (v, cen, 0);
                dfs (v, cen, 1);
            }
        }
        Clear(cen);
        iter (&v, ke[cen]) {
            if (!del[v]) {
                dfs (v, cen, 1);
                int delta = nChild[cen] - nChild[v];
                maximize(Ans[delta], ST.get (delta, n) + 1);
                dfs (v, cen, 3);
                ST.update (delta, 0);
                dfs (v, cen, 0);
                ST.update (delta, -INF);
            }
        }
        del[cen] = 1;
        iter (&v, ke[cen]) {
            if (!del[v]) {
                cen_dcps(v);
            }
        }
    }

    void solution() {
        ST.init(n);
        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);
    }
//    pdfs(1, 0);
//    if (n <= 16) sub1 :: solution();
//    else
        sub5 :: solution();
//    rep (i, 1, n) {
//        if (i & 1) cout << 1 <<"\n";
//        else {
//            cout << Diameter <<"\n";
//            Diameter -= 2;
//        }
//    }

}
#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 member function 'void sub5::Segment_Tree::update(int, int, int, int, int)':
meetings2.cpp:56:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |             int mid = l + r >> 1;
      |                       ~~^~~
meetings2.cpp: In member function 'int sub5::Segment_Tree::get(int, int, int, int, int)':
meetings2.cpp:65:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |             int mid = l + r >> 1;
      |                       ~~^~~
meetings2.cpp: In function 'void sub1::solution()':
meetings2.cpp:184:46: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  184 |                 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