Submission #366472

#	Time	Username	Problem	Language	Result	Execution time	Memory
366472		ne4eHbKa	Papričice (COCI20_papricice)	C++17	50 / 110	356 ms	45932 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef long long ll;
#define int ll
typedef pair<int, int> pii;
typedef long double ld;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

const int N = 4e5 + 5;
int n;
list<int> g[N];
int tin[N], tout[N], timer, si[N];

struct tree {
    tree *l{}, *r{};
    pii v{+inf, -inf};
    tree(int tl = 0, int tr = n) {
        if(tl < tr) {
            int tm = tl + tr >> 1;
            l = new tree(tl, tm);
            r = new tree(tm + 1, tr);
        }
    }
    void add(int u, int tl = 0, int tr = n) {
        umin(v.ft, tout[u]);
        umax(v.sd, tin[u]);
        if(tl == tr) return;
        int tm = tl + tr >> 1;
        si[u] <= tm
            ? l->add(u, tl, tm)
            : r->add(u, tm + 1, tr);
    }
    pii get(int L, int R, int tl = 0, int tr = n) {
        if(L > R) return {+inf, -inf};
        if(L == tl && R == tr) return v;
        int tm = tl + tr >> 1;
        pii le = l->get(L, min(R, tm), tl, tm); ++tm;
        pii ri = r->get(max(tm, L), R, tm, tr);
        return {min(le.ft, ri.ft), max(le.sd, ri.sd)};
    }
} *t;

void init(int v = 0, int pr = -1) {
    tin[v] = timer++;
    si[v] = 1;
    g[v].remove(pr);
    for(int u : g[v])
        init(u, v),
        si[v] += si[u];
    tout[v] = timer++;
}

set<int> f, fg;

int dfs(int v = 0) {
    int a = si[v];
    int res = +inf;
    if(!f.empty()) {
        auto it = f.lower_bound(a + (n - a + 1 >> 1));
        if(it != f.end()) {
            int b = *it - a;
            int c = n - a - b;
            if(b > c) swap(b, c);
            umin(res, max(abs(b - c), max(
                          abs(a - b),
                          abs(a - c))));
        }
        auto it2 = fg.lower_bound(n - a + 1 >> 1);
        if(it2 != fg.end()) {
            int b = *it2;
            int c = n - a - b;
            umin(res, max(abs(b - c), max(
                          abs(a - b),
                          abs(a - c))));
        }
    }
    if(!g[v].empty()) {
        f.insert(a);
        fg.insert(n - a);
        for(int u : g[v])
            umin(res, dfs(u));
        f.erase(a);
        fg.erase(n - a);
    }
    return res;
}

bool works(int d) {
    for(int i = 0; i < n; ++i) {
        int a = si[i];
        if(a * 3 > n) continue;
        if(a * 3 + d * 2 < n) continue;
        pii z = t->get(max(a, n - a - a - d),
                       min(n - a - a, a + d));
        if(z.ft < tin[i] || z.sd > tout[i]) return true;
    }
    return false;
}

void solve() {
    cin >> n;
    for(int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    init();
    t = new tree();
    for(int i = 0; i < n; ++i)
        t->add(i);
    int l = 0, r = dfs();
    while(l < r) {
        int m = l + r >> 1;
        works(m)
            ? r = m
            : l = m + 1;
    }
    cout << l << endl;
#ifdef KEK
    timer = 0;
    for(int i = 0; i < n; ++i)
        g[i].clear();
    f.clear();
    fg.clear();
#endif // KEK
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Compilation message (stderr)

papricice.cpp: In constructor 'tree::tree(ll, ll)':
papricice.cpp:40:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
papricice.cpp: In member function 'void tree::add(ll, ll, ll)':
papricice.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
papricice.cpp: In member function 'pii tree::get(ll, ll, ll, ll)':
papricice.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
papricice.cpp: In function 'll dfs(ll)':
papricice.cpp:80:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         auto it = f.lower_bound(a + (n - a + 1 >> 1));
      |                                      ~~~~~~^~~
papricice.cpp:89:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         auto it2 = fg.lower_bound(n - a + 1 >> 1);
      |                                   ~~~~~~^~~
papricice.cpp: In function 'void solve()':
papricice.cpp:136:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  136 |         int m = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60