oj.uz

Submission #701922

# Submission time Handle Problem Language Result Execution time Memory
701922 2023-02-22T10:56:21 Z Chal1shkan Papričice (COCI20_papricice) C++14
15 / 110
 5 ms 5212 KB 
# 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 3 ms 5024 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct

Subtask #2
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 3 ms 5024 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Incorrect 5 ms 5212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
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 3 ms 5024 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5020 KB Output is correct
6 Incorrect 5 ms 5212 KB Output isn't correct
7 Halted 0 ms 0 KB -