Submission #1028483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028483		underwaterkillerwhale	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	2 ms	4956 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];
    int a[N];
    int Ans[N];

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

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

    vector<pair<int,int>> vec;
    void dfs (int u, int p) {
        int up;{
            int lf = 0, rt = SZ(vec) - 1;
            while (lf < rt) {

                int mid = lf + rt >> 1;
                if (vec[mid].fs >= nChild[u]) rt = mid;
                else lf = mid + 1;
            }
            if (!vec.empty() && vec[lf].fs >= nChild[u]) up = lf;
            else up = SZ(vec);
        }
        if (up != SZ(vec)) {
            maximize(Ans[nChild[u]], high[u] - vec[up].se + 1);
        }
        --up;
        if (!vec.empty() && up >= 0) {
            maximize(Ans[vec[up].fs], high[u] - vec[up].se + 1);
        }
        iter (&v, ke[u]) {
            if (v != p) {
                pre[u] = pre[p] + nChild[u] - nChild[v];
                vec.push_back(mp(pre[u], high[u]));
                dfs (v, u);
                vec.pop_back();
            }
        }
    }

    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 sub5::dfs(int, int)':
meetings2.cpp:56:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |                 int mid = lf + rt >> 1;
      |                           ~~~^~~~
meetings2.cpp: In function 'void sub1::solution()':
meetings2.cpp:117:46: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  117 |                 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: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80