oj.uz

Submission #701889

# Submission time Handle Problem Language Result Execution time Memory
701889 2023-02-22T09:36:28 Z Chal1shkan Papričice (COCI20_papricice) C++14
50 / 110
 180 ms 15880 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 = 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 = u + 1; v <= n; ++v)
        {
            vector <int> x;
            if (is_anc(u, v))
            {
                x.pb(sz[v]);
                x.pb(sz[u] - sz[v]);
                x.pb(n - sz[u]);
            }
            else if (is_anc(v, u))
            {
                x.pb(sz[u]);
                x.pb(sz[v] - sz[u]);
                x.pb(n - sz[v]);
            }
            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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5844 KB Output is correct
2 Correct 5 ms 5844 KB Output is correct
3 Correct 5 ms 5800 KB Output is correct
4 Correct 5 ms 5844 KB Output is correct
5 Correct 5 ms 5736 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5844 KB Output is correct
2 Correct 5 ms 5844 KB Output is correct
3 Correct 5 ms 5800 KB Output is correct
4 Correct 5 ms 5844 KB Output is correct
5 Correct 5 ms 5736 KB Output is correct
6 Correct 180 ms 15880 KB Output is correct
7 Correct 167 ms 14108 KB Output is correct
8 Correct 180 ms 14112 KB Output is correct
9 Correct 169 ms 14352 KB Output is correct
10 Correct 168 ms 15284 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5844 KB Output is correct
2 Correct 5 ms 5844 KB Output is correct
3 Correct 5 ms 5800 KB Output is correct
4 Correct 5 ms 5844 KB Output is correct
5 Correct 5 ms 5736 KB Output is correct
6 Correct 180 ms 15880 KB Output is correct
7 Correct 167 ms 14108 KB Output is correct
8 Correct 180 ms 14112 KB Output is correct
9 Correct 169 ms 14352 KB Output is correct
10 Correct 168 ms 15284 KB Output is correct
11 Runtime error 7 ms 10048 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -