Submission #1028552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028552		underwaterkillerwhale	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	4050 ms	35452 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 ll INF = 2e9;
const int BASE = 1337;

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

namespace sub5 {
    int m;

    int nChild[N], par[N], high[N], pre[N], pa[N][21];
    int a[N];
    int Ans[N];

    void pdfs (int u, int p) {
        nChild[u] = 1;
        par[u] = p;
        high[u] = high[p] + 1;
        pa[u][0] = p; rep (i, 1, 20) pa[u][i] = pa[pa[u][i - 1]][i - 1];
        iter (&v, ke[u]) {
            if (v != p) {
                pdfs (v, u);
                nChild[u] += nChild[v];
            }
        }
    }

    int LCA (int u, int v) {
        if (high[u] > high[v]) swap(u, v);
        int delta = high[v] - high[u];
        rep (i, 0, 20) if (bit(delta, i)) {
            v = pa[v][i];
        }
        if (v == u)
            return v;
        reb (i, 20, 0)
            if (pa[v][i] != pa[u][i]) {
                v = pa[v][i];
                u = pa[u][i];
            }
        return pa[u][0];
    }
    int Dist (int u, int v) {
        return high[u] + high[v] - 2 * high[LCA(u, v)];
    }

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

    set<pair<int,int>> vec;
    void dfs (int u, int p) {
        iter (&id, vec) {
            maximize(Ans[min(nChild[u], id.fs)], Dist(u, id.se) + 1);
//            cout << u <<" "<<id.se <<"\n";
        }
        iter (&v, ke[u]) {
            if (v != p) {
                pre[u] = pre[p] + nChild[u] - nChild[v];
                vec.insert(mp(pre[u], u));
                dfs (v, u);
                vec.erase(vec.find(mp(pre[u], u)));
            }
        }
        vec.insert(mp(nChild[u], u));
    }

    void solution() {
        pdfs (1, 0);
        rep (i, 1, n + 1) Ans[i] = 1;
        dfs (1, 0);
        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 function 'void sub1::solution()':
meetings2.cpp:122:46: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  122 |                 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: 0 / 80