Submission #366828

#	Time	Username	Problem	Language	Result	Execution time	Memory
366828		topovik	Papričice (COCI20_papricice)	C++14	50 / 110	1085 ms	20628 KiB

papricice

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

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