oj.uz

Submission #706602

# Submission time Handle Problem Language Result Execution time Memory
706602 2023-03-07T06:30:26 Z YugiHacker Papričice (COCI20_papricice) C++14
110 / 110
 207 ms 23444 KB 
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 200005
using namespace std;
int n, sz[maxn], ans = 1e9;
vector <int> a[maxn];
void dfs(int u, int p)
{
    sz[u] = 1;
    for (int v:a[u]) if (v!=p)
    {
        dfs(v, u);
        sz[u] += sz[v];
    }
}
set <int> A, B;
/*
set A: contain all vertices from root to parent of u
B - Root - |szA - | sz[u]: 3 parts: n - szA, szA - sz[u], sz[u]
set B: contain all vertices visited and not in A
B - | Root - | sz[u]: 3 parts: szB, n - szB - sz[u], sz[u]
*/
int optimize(int a, int b, int c)
{
    return max({a, b, c}) - min({a, b, c});
}
vector <int> closest(set <int> &s, int x)
{
    vector <int> v;
    auto it = s.lower_bound(x);
    if (it != s.end()) v.push_back(*it);
    if (it != s.begin())
    {
        --it;
        v.push_back(*it);
    }
    return v;
}
void dfs2(int u, int p)
{
    for (int szA: closest(A, (n + sz[u])/2))
        ans = min(ans, optimize(sz[u], szA - sz[u], n-szA));
    for (int szB: closest(B, (n - sz[u])/2))
        ans = min(ans, optimize(sz[u], szB, n-sz[u]-szB));
    A.insert(sz[u]);
    for (int v:a[u]) if (v!=p)
        dfs2(v, u);
    A.erase(sz[u]);
    B.insert(sz[u]);
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    f1 (i, n-1)
    {
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1, 0);
    dfs2(1, 0);
    cout << ans;
}

Compilation message

papricice.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main()
      | ^~~~

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 5020 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 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 5020 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5040 KB Output is correct
7 Correct 4 ms 5032 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5076 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 5020 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5040 KB Output is correct
7 Correct 4 ms 5032 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 157 ms 14708 KB Output is correct
12 Correct 207 ms 14752 KB Output is correct
13 Correct 159 ms 15072 KB Output is correct
14 Correct 157 ms 14864 KB Output is correct
15 Correct 189 ms 14624 KB Output is correct
16 Correct 117 ms 14508 KB Output is correct
17 Correct 166 ms 14760 KB Output is correct
18 Correct 192 ms 23444 KB Output is correct
19 Correct 178 ms 14736 KB Output is correct
20 Correct 189 ms 14868 KB Output is correct