oj.uz

Submission #366480

# Submission time Handle Problem Language Result Execution time Memory
366480 2021-02-14T09:07:18 Z ne4eHbKa Papričice (COCI20_papricice) C++17
110 / 110
 319 ms 33132 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 9 ms 9964 KB Output is correct
7 Correct 8 ms 9984 KB Output is correct
8 Correct 8 ms 9964 KB Output is correct
9 Correct 8 ms 9964 KB Output is correct
10 Correct 8 ms 9964 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9728 KB Output is correct
6 Correct 9 ms 9964 KB Output is correct
7 Correct 8 ms 9984 KB Output is correct
8 Correct 8 ms 9964 KB Output is correct
9 Correct 8 ms 9964 KB Output is correct
10 Correct 8 ms 9964 KB Output is correct
11 Correct 299 ms 27008 KB Output is correct
12 Correct 319 ms 27116 KB Output is correct
13 Correct 267 ms 26988 KB Output is correct
14 Correct 306 ms 27116 KB Output is correct
15 Correct 305 ms 26988 KB Output is correct
16 Correct 179 ms 26988 KB Output is correct
17 Correct 274 ms 27116 KB Output is correct
18 Correct 287 ms 33132 KB Output is correct
19 Correct 273 ms 28012 KB Output is correct
20 Correct 283 ms 28040 KB Output is correct