oj.uz

Submission #698476

# Submission time Handle Problem Language Result Execution time Memory
698476 2023-02-13T15:23:16 Z tamthegod Papričice (COCI20_papricice) C++17
110 / 110
 359 ms 53668 KB 
// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n;
vector<int> adj[maxN];
int p[maxN], sz[maxN];
int tin[maxN], tout[maxN], Time = 0;
void ReadInput()
{
    cin >> n;
    for(int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
}
void dfs(int u)
{
    sz[u] = 1;
    tin[u] = ++Time;
    for(int v : adj[u])
    {
        if(v == p[u]) continue;
        p[v] = u;
        dfs(v);
        sz[u] += sz[v];
    }
    tout[u] = Time;
}
multiset<int> S1, S2;
int res = oo;
void DFS(int u)
{
    S1.insert(sz[u]);
    S2.erase(S2.find(sz[u]));
    int tmp = (n + sz[u]) / 2;
    auto it = S1.lower_bound(tmp);
    if(it != S1.end())
    {
        int sz1 = sz[u], sz2 = *it - sz[u], sz3 = n - sz1 - sz2;
        res = min(res, max({abs(sz1 - sz2), abs(sz2 - sz3), abs(sz1 - sz3)}));
    }
    if(it != S1.begin())
    {
        it--;
        int sz1 = sz[u], sz2 = *it - sz[u], sz3 = n - sz1 - sz2;
        res = min(res, max({abs(sz1 - sz2), abs(sz2 - sz3), abs(sz1 - sz3)}));
    }
    tmp = (n - sz[u]) / 2;
    it = S2.upper_bound(tmp);
    if(it != S2.end() && *it >= sz[u])
    {
        int sz1 = sz[u], sz2 = *it, sz3 = n - sz1 - sz2;
        res = min(res, max({abs(sz1 - sz2), abs(sz2 - sz3), abs(sz1 - sz3)}));
    }
    if(it != S2.begin())
    {
        it--;
        if(*it >= sz[u])
        {
            int sz1 = sz[u], sz2 = *it, sz3 = n - sz1 - sz2;
            res = min(res, max({abs(sz1 - sz2), abs(sz2 - sz3), abs(sz1 - sz3)}));
        }
    }
    for(int v : adj[u])
    {
        if(v == p[u]) continue;
        DFS(v);
    }
    S1.erase(S1.find(sz[u]));
    S2.insert(sz[u]);
}
void Solve()
{
    dfs(1);
    for(int i=1; i<=n; i++)
        S2.insert(sz[i]);
    DFS(1);
    cout << res;
}
int32_t main()
{
    //freopen("sol.inp", "r", stdin);
    // freopen("sol.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23816 KB Output is correct
2 Correct 13 ms 23828 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 13 ms 23844 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23816 KB Output is correct
2 Correct 13 ms 23828 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 13 ms 23844 KB Output is correct
6 Correct 14 ms 24020 KB Output is correct
7 Correct 13 ms 24020 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 14 ms 24088 KB Output is correct
10 Correct 14 ms 24088 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23816 KB Output is correct
2 Correct 13 ms 23828 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 13 ms 23844 KB Output is correct
6 Correct 14 ms 24020 KB Output is correct
7 Correct 13 ms 24020 KB Output is correct
8 Correct 13 ms 24020 KB Output is correct
9 Correct 14 ms 24088 KB Output is correct
10 Correct 14 ms 24088 KB Output is correct
11 Correct 312 ms 49400 KB Output is correct
12 Correct 338 ms 49324 KB Output is correct
13 Correct 277 ms 49980 KB Output is correct
14 Correct 282 ms 49692 KB Output is correct
15 Correct 359 ms 49316 KB Output is correct
16 Correct 234 ms 49084 KB Output is correct
17 Correct 296 ms 49376 KB Output is correct
18 Correct 310 ms 53668 KB Output is correct
19 Correct 298 ms 49704 KB Output is correct
20 Correct 328 ms 49352 KB Output is correct