oj.uz

Submission #1028595

# Submission time Handle Problem Language Result Execution time Memory
1028595 2024-07-20T05:45:45 Z underwaterkillerwhale Meetings 2 (JOI21_meetings2) C++17
100 / 100
 2414 ms 31312 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8604 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8616 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8604 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8616 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 12 ms 8796 KB Output is correct
23 Correct 12 ms 8792 KB Output is correct
24 Correct 13 ms 8796 KB Output is correct
25 Correct 11 ms 8848 KB Output is correct
26 Correct 10 ms 8796 KB Output is correct
27 Correct 10 ms 8796 KB Output is correct
28 Correct 10 ms 8860 KB Output is correct
29 Correct 10 ms 8844 KB Output is correct
30 Correct 12 ms 9052 KB Output is correct
31 Correct 11 ms 8848 KB Output is correct
32 Correct 17 ms 8796 KB Output is correct
33 Correct 19 ms 8968 KB Output is correct
34 Correct 5 ms 8792 KB Output is correct
35 Correct 4 ms 8796 KB Output is correct
36 Correct 12 ms 8872 KB Output is correct
37 Correct 5 ms 8796 KB Output is correct
38 Correct 11 ms 8796 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8604 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8616 KB Output is correct
16 Correct 2 ms 8540 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 12 ms 8796 KB Output is correct
23 Correct 12 ms 8792 KB Output is correct
24 Correct 13 ms 8796 KB Output is correct
25 Correct 11 ms 8848 KB Output is correct
26 Correct 10 ms 8796 KB Output is correct
27 Correct 10 ms 8796 KB Output is correct
28 Correct 10 ms 8860 KB Output is correct
29 Correct 10 ms 8844 KB Output is correct
30 Correct 12 ms 9052 KB Output is correct
31 Correct 11 ms 8848 KB Output is correct
32 Correct 17 ms 8796 KB Output is correct
33 Correct 19 ms 8968 KB Output is correct
34 Correct 5 ms 8792 KB Output is correct
35 Correct 4 ms 8796 KB Output is correct
36 Correct 12 ms 8872 KB Output is correct
37 Correct 5 ms 8796 KB Output is correct
38 Correct 11 ms 8796 KB Output is correct
39 Correct 1287 ms 19960 KB Output is correct
40 Correct 1233 ms 19708 KB Output is correct
41 Correct 1187 ms 20048 KB Output is correct
42 Correct 1158 ms 20072 KB Output is correct
43 Correct 1219 ms 20072 KB Output is correct
44 Correct 1206 ms 20080 KB Output is correct
45 Correct 2414 ms 25924 KB Output is correct
46 Correct 2324 ms 31312 KB Output is correct
47 Correct 314 ms 20428 KB Output is correct
48 Correct 196 ms 20544 KB Output is correct
49 Correct 1442 ms 20820 KB Output is correct
50 Correct 293 ms 20760 KB Output is correct
51 Correct 1207 ms 26548 KB Output is correct