Submission #701427

#	Time	Username	Problem	Language	Result	Execution time	Memory
701427		Chal1shkan	Papričice (COCI20_papricice)	C++14	0 / 110	6 ms	5844 KiB

papricice

# 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 = 1e18 + 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, timer;
vector <int> g[maxn];
int sz[maxn];
int tin[maxn];
int tout[maxn];
int a[2003][2003];

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

bool is_anc (int u, int v)
{
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

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);
        a[u][v] = 1;
        a[v][u] = 1;
    }
    dfs(1);
    int ans = n;
    for (int u = 1; u <= n; ++u)
    {
        for (int v = 1; v <= n; ++v)
        {
            if (u != v && !a[u][v] && !a[v][u])
            {
                vector <int> x;
                if (is_anc(u, v))
                {
                    x.pb(sz[v]);
                    x.pb(sz[u] - sz[v] - 1);
                    x.pb(n - sz[u] + 1);
                }
                else if (is_anc(v, u))
                {
                    x.pb(sz[u]);
                    x.pb(sz[v] - sz[u] - 1);
                    x.pb(n - sz[v] + 1);
                }
                else
                {
                    x.pb(sz[u]);
                    x.pb(sz[v]);
                    x.pb(n - sz[u] - sz[v]);
                }
                sort(x.begin(), x.end());
                ans = min(ans, x.back() - x[0]);
            }
        }
    }
    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: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60