Submission #701918

#	Time	Username	Problem	Language	Result	Execution time	Memory
701918		Chal1shkan	Papričice (COCI20_papricice)	C++14	110 / 110	244 ms	29424 KiB

papricice

// 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 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60