oj.uz

Submission #701918

# Submission time Handle Problem Language Result Execution time Memory
701918 2023-02-22T10:41:31 Z Chal1shkan Papričice (COCI20_papricice) C++14
110 / 110
 244 ms 29424 KB 
// C:\Programs\gcc11-64-winlibs\include\c++\11.2.0\x86_64-w64-mingw32\bits

# include <bits/stdc++.h>

# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll maxn = 2e5 + 25;
const ll inf = 2e9 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;

int n, ans = inf;
vector <int> g[maxn];
int sz[maxn];
bool used[maxn];
multiset <int> a, b;

void dfs_calc (int v)
{
    sz[v] = 1;
    for (int to : g[v])
    {
        if (!sz[to])
        {
            dfs_calc(to);
            sz[v] += sz[to];
        }
    }
}

vector <int> f (multiset <int>& s, int x)
{
    vector <int> res;
    auto it = s.lower_bound(x);
    if (it != s.end())
    {
        res.pb(*it);
    }
    if (it != s.begin())
    {
        it--;
        res.pb(*it);
    }
    return res;
}

int mx_mn (int x, int y, int z)
{
    return max({x, y, z}) - min({x, y, z});
}

void dfs (int v)
{
    used[v] = 1;
    for (int x : f(a, (n + sz[v]) / 2))
    {
        ans = min(ans, mx_mn(sz[v], x - sz[v], n - x));
    }
    for (int x : f(b, (n - sz[v]) / 2))
    {
        ans = min(ans, mx_mn(sz[v], x, n - x - sz[v]));
    }
    a.insert(sz[v]);
    for (int to : g[v])
    {
        if (!used[to])
        {
            dfs(to);
        }
    }
    a.erase(a.find(sz[v]));
    b.insert(sz[v]);
}

void ma1n (/* SABR */)
{
    cin >> n;
    for (int i = 1, u, v; i < n; ++i)
    {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs_calc(1);
    dfs(1);
    cout << ans;    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 5196 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 5196 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 224 ms 24144 KB Output is correct
12 Correct 240 ms 24260 KB Output is correct
13 Correct 187 ms 24584 KB Output is correct
14 Correct 209 ms 24388 KB Output is correct
15 Correct 241 ms 24216 KB Output is correct
16 Correct 169 ms 24100 KB Output is correct
17 Correct 204 ms 24228 KB Output is correct
18 Correct 244 ms 29424 KB Output is correct
19 Correct 204 ms 24360 KB Output is correct
20 Correct 239 ms 24220 KB Output is correct