Submission #410176

#	Time	Username	Problem	Language	Result	Execution time	Memory
410176		jhwest2	Meetings 2 (JOI21_meetings2)	C++14	20 / 100	4056 ms	27156 KiB

meetings2

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int M = 2e5 + 10;
const int INF = 1e9 + 10;

int n, Sub[M], Chk[M], Dep[M];
vector<int> G[M];

struct SEG {
    int T[M << 2], L[M << 2];

    void init() {
        for (int i = 0; i < M << 2; i++) L[i] = -2 * INF;
    }
    void push(int lo, int hi, int idx) {
        if (L[idx] == -2 * INF) return;
        if (lo != hi) {
            L[idx << 1] = L[idx];
            L[idx << 1 | 1] = L[idx];
        }
        T[idx] = L[idx]; L[idx] = -2 * INF;
    }
    int update(int a, int b, int x, int lo = 1, int hi = n, int idx = 1) {
        push(lo, hi, idx);
        if (b < lo || a > hi) return T[idx];
        if (a <= lo && hi <= b) {
            L[idx] = x; push(lo, hi, idx); return T[idx];
        }
        return T[idx] = max(update(a, b, x, lo, lo + hi >> 1, idx << 1), update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1));
    }
    int query(int a, int lo = 1, int hi = n, int idx = 1) {
        push(lo, hi, idx);
        if (lo == hi) return T[idx];
        if (a <= lo + hi >> 1) return query(a, lo, lo + hi >> 1, idx << 1);
        else return query(a, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
    }
    int find(int x, int lo = 1, int hi = n, int idx = 1) {
        push(lo, hi, idx);
        if (lo == hi) {
            if (T[idx] >= x) return lo;
            return lo - 1;
        }
        push(1 + (lo + hi >> 1), hi, idx << 1 | 1);
        if (T[idx << 1 | 1] >= x) return find(x, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
        return find(x, lo, lo + hi >> 1, idx << 1);
    }
} S, Ans;


void dfs(int p, int cur) {
    Sub[cur] = 1;
    for (int x : G[cur]) if (p != x && !Chk[x]) {
        dfs(cur, x); Sub[cur] += Sub[x];
    }
}
int cent(int p, int cur, int s) {
    for (int x : G[cur]) if (p != x && !Chk[x]) {
        if (Sub[x] > s / 2) return cent(cur, x, s);
    }
    return cur;
}
void dfs2(int p, int cur) {
    if (Chk[cur]) return; Sub[cur] = 1;
    for (int x : G[cur]) if (p != x) {
        Dep[x] = Dep[cur] + 1;
        dfs2(cur, x); Sub[cur] += Sub[x];
    }
}
void dp(int p, int cur) {
    for (int x : G[cur]) if (p != x && !Chk[x]) {
        dp(cur, x);
    }
    int a = S.query(Sub[cur]);
    if (a == -INF) return;

    int k = Ans.find(Dep[cur] + a);
    Ans.update(k + 1, Sub[cur], Dep[cur] + a);
}
void update(int p, int cur) {
    int k = S.find(Dep[cur]);
    S.update(k + 1, Sub[cur], Dep[cur]);
    for (int x : G[cur]) if (p != x && !Chk[x]) {
        update(cur, x);
    }
}
void solve(int cur) {
    dfs(cur, cur); int k = cent(cur, cur, Sub[cur]);
    Dep[k] = 0; Sub[k] = 1;
    S.update(1, n, -INF);
    for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
        int x = G[k][i]; Dep[x] = 1;
        dfs2(k, x);
        int l = S.find(0);
        S.update(l + 1, n - Sub[x], 0);
        dp(k, x); update(k, x);
        l = S.find(1);
        S.update(l + 1, n - Sub[x], -INF);
    }
    S.update(1, n, -INF);
    for (int i = G[k].size() - 1; i >= 0; i--) if (!Chk[G[k][i]]) {
        int x = G[k][i];
        dp(k, x); update(k, x);
    }

    Chk[k] = 1;
    vector<int> V(G[k].size());
    for (int i = 0; i < G[k].size(); i++) V[i] = Sub[G[k][i]];
    for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
        Sub[k] = n - V[i]; solve(G[k][i]);
    }
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y); G[y].push_back(x);
    }
    S.init(); solve(1);
    for (int i = 1; i <= n; i++) {
        if (i & 1) cout << 1 << '\n';
        else cout << Ans.query(i / 2) + 1 << '\n';
    }
}

Compilation message (stderr)

meetings2.cpp: In member function 'int SEG::update(int, int, int, int, int, int)':
meetings2.cpp:36:52: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         return T[idx] = max(update(a, b, x, lo, lo + hi >> 1, idx << 1), update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1));
      |                                                 ~~~^~~~
meetings2.cpp:36:98: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         return T[idx] = max(update(a, b, x, lo, lo + hi >> 1, idx << 1), update(a, b, x, 1 + (lo + hi >> 1), hi, idx << 1 | 1));
      |                                                                                               ~~~^~~~
meetings2.cpp: In member function 'int SEG::query(int, int, int, int)':
meetings2.cpp:41:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         if (a <= lo + hi >> 1) return query(a, lo, lo + hi >> 1, idx << 1);
      |                  ~~~^~~~
meetings2.cpp:41:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         if (a <= lo + hi >> 1) return query(a, lo, lo + hi >> 1, idx << 1);
      |                                                    ~~~^~~~
meetings2.cpp:42:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         else return query(a, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
      |                                   ~~~^~~~
meetings2.cpp: In member function 'int SEG::find(int, int, int, int)':
meetings2.cpp:50:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         push(1 + (lo + hi >> 1), hi, idx << 1 | 1);
      |                   ~~~^~~~
meetings2.cpp:51:58: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         if (T[idx << 1 | 1] >= x) return find(x, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
      |                                                       ~~~^~~~
meetings2.cpp:52:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         return find(x, lo, lo + hi >> 1, idx << 1);
      |                            ~~~^~~~
meetings2.cpp: In function 'void dfs2(int, int)':
meetings2.cpp:70:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   70 |     if (Chk[cur]) return; Sub[cur] = 1;
      |     ^~
meetings2.cpp:70:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   70 |     if (Chk[cur]) return; Sub[cur] = 1;
      |                           ^~~
meetings2.cpp: In function 'void solve(int)':
meetings2.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
      |                     ~~^~~~~~~~~~~~~
meetings2.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int i = 0; i < G[k].size(); i++) V[i] = Sub[G[k][i]];
      |                     ~~^~~~~~~~~~~~~
meetings2.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
      |                     ~~^~~~~~~~~~~~~

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