제출 #366833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366833		topovik	Papričice (COCI20_papricice)	C++14	50 / 110	1085 ms	18152 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]);
    for (int i = 0; i < a[x].size(); i++) sort(pr[i].begin(), pr[i].end());
    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 (int j1 = 0; j1 < pr[nom1].size(); j1++)
        {
              for (int j = 0; j < pr[nom].size(); j++) ans = min(ans, max(n - pr[nom1][j1] - pr[nom][j], max(pr[nom1][j1], pr[nom][j])) - min(n - pr[nom1][j1] - pr[nom][j], min(pr[nom1][j1], pr[nom][j])));
            int ps;
            auto j = lower_bound(pr[nom].begin(), pr[nom].end(), pr[nom1][j1]);
            if (j != pr[nom].end())
            {
                ps = j - pr[nom].begin();
                ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
            }
            j = upper_bound(pr[nom].begin(), pr[nom].end(), pr[nom1][j1]);
            if (j != pr[nom].end())
            {
                ps = j - pr[nom].begin();
                ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
            }
            int l = 0, r = pr[nom].size() - 1;
            while (l < r)
            {
                int mdl = (l + r + 1) >> 1;
                if (n - pr[nom1][j1] - pr[nom][mdl] < pr[nom1][j1]) r = mdl - 1;
                else l = mdl;
            }
            {
                ps = l;
                ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
            }
            l++;
            if (l < pr[nom].size())
            {
                ps = l;
                ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
            }
            l = 0, r = pr[nom].size() - 1;
            while (l < r)
            {
                int mdl = (l + r + 1) >> 1;
                if (n - pr[nom1][j1] - pr[nom][mdl] < pr[nom1][j1]) r = mdl - 1;
                else l = mdl;
            }
            {
                ps = l;
                ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
            }
            l++;
            if (l < pr[nom].size())
            {
                ps = l;
                ans = min(ans, max(n - pr[nom1][j1] - pr[nom][ps], max(pr[nom1][j1], pr[nom][ps])) - min(n - pr[nom1][j1] - pr[nom][ps], min(pr[nom1][j1], pr[nom][ps])));
            }
        }
        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;
}

컴파일 시 표준 에러 (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:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < a[x].size(); i++) sort(pr[i].begin(), pr[i].end());
      |                     ~~^~~~~~~~~~~~~
papricice.cpp:67: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]
   67 |     for (ll i = 1; i < a[x].size(); i++)
      |                    ~~^~~~~~~~~~~~~
papricice.cpp:71:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int j1 = 0; j1 < pr[nom1].size(); j1++)
      |                          ~~~^~~~~~~~~~~~~~~~~
papricice.cpp:73:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |               for (int j = 0; j < pr[nom].size(); j++) ans = min(ans, max(n - pr[nom1][j1] - pr[nom][j], max(pr[nom1][j1], pr[nom][j])) - min(n - pr[nom1][j1] - pr[nom][j], min(pr[nom1][j1], pr[nom][j])));
      |                               ~~^~~~~~~~~~~~~~~~
papricice.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             if (l < pr[nom].size())
      |                 ~~^~~~~~~~~~~~~~~~
papricice.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             if (l < pr[nom].size())
      |                 ~~^~~~~~~~~~~~~~~~
papricice.cpp:122: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]
  122 |         for (ll j = 0; j < pr[nom1].size(); j++) pr[nom].pb(pr[nom1][j]);
      |                        ~~^~~~~~~~~~~~~~~~~
papricice.cpp:124: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]
  124 |     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