제출 #366833

#제출 시각아이디문제언어결과실행 시간메모리
366833topovikPapričice (COCI20_papricice)C++14
50 / 110
1085 ms18152 KiB
#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]);
      |                    ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...