oj.uz

Submission #366828

# Submission time Handle Problem Language Result Execution time Memory
366828 2021-02-15T10:42:59 Z topovik Papričice (COCI20_papricice) C++14
50 / 110
 1000 ms 20628 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second

using namespace std;

typedef long long ll;

const ll oo = 1e9;
const ll N = 1e6;

vector <vector <ll> > a;
ll sz[N];
ll sub_sz[N];
ll kol;
ll n;
bool mrk[N];
ll ans = oo;

ll calcsz(ll x, ll y)
{
    sz[x] = 1;
    for (ll i = 0; i < a[x].size(); i++)
        if (a[x][i] != y) sz[x] += calcsz(a[x][i], x);
    return sz[x];
}

ll calc(ll x, ll y)
{
    sub_sz[x] = 1;
    if (mrk[x]) return sub_sz[x];
    for (ll i = 0;  i < a[x].size(); i++)
        if (a[x][i] != y) sub_sz[x] += calc(a[x][i], x);
    return sub_sz[x];
}

ll find_centroid(ll x, ll y)
{
    for (ll i = 0; i < a[x].size(); i++)
        if (a[x][i] != y && !mrk[a[x][i]] && sub_sz[a[x][i]] >= kol / 2) return find_centroid(a[x][i], x);
    return x;
}

void Rec(ll x, ll y, vector <ll> *k)
{
    if (sz[x] > sz[y]) k -> pb(n - sz[y]);
    else               k -> pb(sz[x]);
    if (mrk[x]) return;
    for (ll i = 0; i < a[x].size(); i++)
        if (a[x][i] != y) Rec(a[x][i], x, k);
}

void Centr_Tree(ll x)
{
    if (mrk[x]) return;
    kol = calc(x, x);
    x = find_centroid(x, x);
    mrk[x] = 1;


    vector <ll> pr[a[x].size()];
    for (ll i = 0; i < a[x].size(); i++) pr[i].clear();
    for (ll i = 0; i < a[x].size(); i++) Rec(a[x][i], x, &pr[i]);
    ll nom = 0;
    for (ll i = 1; i < a[x].size(); i++)
    {
        ll nom1 = i;
        if (pr[nom1].size() > pr[nom].size()) swap(nom, nom1);
        for (ll j = 0; j < pr[nom].size(); j++)
            for (ll j1 = 0; j1 < pr[nom1].size(); j1++) ans = min(ans, max(n - pr[nom1][j1] - pr[nom][j], max(pr[nom][j], pr[nom1][j1])) - min(n - pr[nom1][j1] - pr[nom][j], min(pr[nom][j], pr[nom1][j1])));
        for (ll j = 0; j < pr[nom1].size(); j++) pr[nom].pb(pr[nom1][j]);
    }

    for (ll i = 0; i < a[x].size(); i++) Centr_Tree(a[x][i]);
}

int main() {
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    a.resize(n);
    for (ll i = 0; i < n - 1; i++)
    {
        ll x, y;
        cin >> x >> y;
        a[--x].pb(--y);
        a[y].pb(x);
    }
    calcsz(0, 0);
    Centr_Tree(0);
    cout << ans;
}

Compilation message

papricice.cpp: In function 'll calcsz(ll, ll)':
papricice.cpp:24:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (ll i = 0; i < a[x].size(); i++)
      |                    ~~^~~~~~~~~~~~~
papricice.cpp: In function 'll calc(ll, ll)':
papricice.cpp:33:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (ll i = 0;  i < a[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~
papricice.cpp: In function 'll find_centroid(ll, ll)':
papricice.cpp:40:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (ll i = 0; i < a[x].size(); i++)
      |                    ~~^~~~~~~~~~~~~
papricice.cpp: In function 'void Rec(ll, ll, std::vector<long long int>*)':
papricice.cpp:50:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (ll i = 0; i < a[x].size(); i++)
      |                    ~~^~~~~~~~~~~~~
papricice.cpp: In function 'void Centr_Tree(ll)':
papricice.cpp:63:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (ll i = 0; i < a[x].size(); i++) pr[i].clear();
      |                    ~~^~~~~~~~~~~~~
papricice.cpp:64:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (ll i = 0; i < a[x].size(); i++) Rec(a[x][i], x, &pr[i]);
      |                    ~~^~~~~~~~~~~~~
papricice.cpp:66:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (ll i = 1; i < a[x].size(); i++)
      |                    ~~^~~~~~~~~~~~~
papricice.cpp:70:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (ll j = 0; j < pr[nom].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~
papricice.cpp:71:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for (ll j1 = 0; j1 < pr[nom1].size(); j1++) ans = min(ans, max(n - pr[nom1][j1] - pr[nom][j], max(pr[nom][j], pr[nom1][j1])) - min(n - pr[nom1][j1] - pr[nom][j], min(pr[nom][j], pr[nom1][j1])));
      |                             ~~~^~~~~~~~~~~~~~~~~
papricice.cpp:72:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (ll j = 0; j < pr[nom1].size(); j++) pr[nom].pb(pr[nom1][j]);
      |                        ~~^~~~~~~~~~~~~~~~~
papricice.cpp:75:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (ll i = 0; i < a[x].size(); i++) Centr_Tree(a[x][i]);
      |                    ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 9 ms 620 KB Output is correct
7 Correct 10 ms 620 KB Output is correct
8 Correct 9 ms 748 KB Output is correct
9 Correct 9 ms 620 KB Output is correct
10 Correct 10 ms 620 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 9 ms 620 KB Output is correct
7 Correct 10 ms 620 KB Output is correct
8 Correct 9 ms 748 KB Output is correct
9 Correct 9 ms 620 KB Output is correct
10 Correct 10 ms 620 KB Output is correct
11 Execution timed out 1085 ms 20628 KB Time limit exceeded
12 Halted 0 ms 0 KB -