Submission #366480

#	Time	Username	Problem	Language	Result	Execution time	Memory
366480		ne4eHbKa	Papričice (COCI20_papricice)	C++17	110 / 110	319 ms	33132 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];

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, w;

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

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();
    cout << dfs() << endl;
#ifdef KEK
    timer = 0;
    for(int i = 0; i < n; ++i)
        g[i].clear();
    f.clear();
    w.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 function 'll dfs(ll)':
papricice.cpp:51:40: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   51 |         auto it = f.lower_bound(a + (n - a >> 1));
      |                                      ~~^~~
papricice.cpp:70:35: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   70 |         auto it = w.lower_bound(n - a >> 1);
      |                                 ~~^~~

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