Submission #706602

#	Time	Username	Problem	Language	Result	Execution time	Memory
706602		YugiHacker	Papričice (COCI20_papricice)	C++14	110 / 110	207 ms	23444 KiB

papricice

#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 (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60