Submission #410165

#	Time	Username	Problem	Language	Result	Execution time	Memory
410165		jhwest2	Meetings 2 (JOI21_meetings2)	C++14	20 / 100	4061 ms	29116 KiB

meetings2

#include <bits/stdc++.h>
#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);
    }
} 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 lo = 1, hi = Sub[cur] + 1;
    while (lo < hi) {
        if (Ans.query(lo + hi >> 1) <= Dep[cur] + a) hi = lo + hi >> 1;
        else lo = 1 + (lo + hi >> 1);
    }
    Ans.update(lo, Sub[cur], Dep[cur] + a);
}
void update(int p, int cur) {
    int lo = 1, hi = Sub[cur] + 1;
    while (lo < hi) {
        int m = lo + hi >> 1;
        if (S.query(m) <= Dep[cur]) hi = m;
        else lo = m + 1;
    }
    S.update(lo, 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 lo = 1, hi = n - Sub[x];
        while (lo < hi) {
            int m = lo + hi >> 1;
            if (S.query(m) != -INF) lo = m + 1;
            else hi = m;
        }
        S.update(lo, n - Sub[x], 0);
        dp(k, x); update(k, x);
        lo = 1, hi = n - Sub[x];
        while (lo < hi) {
            int m = lo + hi >> 1;
            if (S.query(m) != 0) lo = m + 1;
            else hi = m;
        }
        S.update(lo, 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:33:52: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         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:33:98: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         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:38:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         if (a <= lo + hi >> 1) return query(a, lo, lo + hi >> 1, idx << 1);
      |                  ~~~^~~~
meetings2.cpp:38:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         if (a <= lo + hi >> 1) return query(a, lo, lo + hi >> 1, idx << 1);
      |                                                    ~~~^~~~
meetings2.cpp:39:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         else return query(a, 1 + (lo + hi >> 1), hi, idx << 1 | 1);
      |                                   ~~~^~~~
meetings2.cpp: In function 'void dfs2(int, int)':
meetings2.cpp:57:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   57 |     if (Chk[cur]) return; Sub[cur] = 1;
      |     ^~
meetings2.cpp:57:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   57 |     if (Chk[cur]) return; Sub[cur] = 1;
      |                           ^~~
meetings2.cpp: In function 'void dp(int, int)':
meetings2.cpp:72:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         if (Ans.query(lo + hi >> 1) <= Dep[cur] + a) hi = lo + hi >> 1;
      |                       ~~~^~~~
meetings2.cpp:72:62: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         if (Ans.query(lo + hi >> 1) <= Dep[cur] + a) hi = lo + hi >> 1;
      |                                                           ~~~^~~~
meetings2.cpp:73:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         else lo = 1 + (lo + hi >> 1);
      |                        ~~~^~~~
meetings2.cpp: In function 'void update(int, int)':
meetings2.cpp:80:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int m = lo + hi >> 1;
      |                 ~~~^~~~
meetings2.cpp: In function 'void solve(int)':
meetings2.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < G[k].size(); i++) if (!Chk[G[k][i]]) {
      |                     ~~^~~~~~~~~~~~~
meetings2.cpp:98:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |             int m = lo + hi >> 1;
      |                     ~~~^~~~
meetings2.cpp:106:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |             int m = lo + hi >> 1;
      |                     ~~~^~~~
meetings2.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < G[k].size(); i++) V[i] = Sub[G[k][i]];
      |                     ~~^~~~~~~~~~~~~
meetings2.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     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