Submission #338697

#TimeUsernameProblemLanguageResultExecution timeMemory
338697souvenir_vaynePapričice (COCI20_papricice)C++14
0 / 110
3 ms4972 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <chrono> #define pb push_back #define INF 0x3f3f3f3f #define LINF 0x3f3f3f3f3f3f3f3f #define int long long #define endl '\n' #define ll long long #define f first #define fin cin #define fout cout #define s second #define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0) #define debug(x) cout << "DEBUG " << x << endl #define debug2(x, y) cout << "DEBUG " << x << " " << y << endl #define debug3(x, y, z) cout << "DEBUG " << x << " " << y << " " << z<< endl #define debug4(x, y, z, o) cout << "DEBUG " << x << " " << y << " " << z<< " " << o << endl #define all(x) x.begin(), x.end() #define left vadia #define lb lower_bound #define right puta using namespace std; using namespace __gnu_pbds; void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str( ),"w",stdout); } typedef pair<ll, ll> pii; typedef vector<vector<char>> mat; typedef pair<int, string> pis; const ll mod = 1e9+7; typedef vector<int> vi; typedef pair<int, pair<int, int>> piii; const int MAXN = 2e5 + 5; int sz[MAXN], n, ans = INT_MAX; vector<int> g[MAXN]; void get(int u, int p) { sz[u] = 1; for(int &i : g[u]) if(i != p) { get(i, u); sz[u] += sz[i]; } } int calc(int x, int y) { int a1 = x, a2 = y - x, a3 = n - y; return max({abs(a1 - a2), abs(a1 - a3), abs(a2 - a3)}); } int calc2(int x, int y) { int a1 = x, a2 = y, a3 = n - x - y; return max({abs(a1 - a2), abs(a1 - a3), abs(a2 - a3)}); } set<int> a, b; void dfs(int u, int p) { if(u != 1) { int ini = sz[u], mid, end = n, best = (n+sz[u])/2; while(ini <= end) { mid = (ini + end) >> 1; if(calc(sz[u], mid) < calc(sz[u], mid + 1)) { end = mid-1; if(calc(sz[u], mid) < calc(sz[u], best)) best = mid; } else { ini = mid + 2; if(calc(sz[u], mid+1) < calc(sz[u], best)) best = mid+1; } } auto it = a.upper_bound(best); if(it != a.end()) ans = min(ans, calc(sz[u], *it)); if(it != a.begin()) { it--; ans = min(ans, calc(sz[u], *it)); } ini = 0, end = n, best = (n-sz[u])/2; while(ini <= end) { mid = (ini + end) >> 1; if(calc2(sz[u], mid) < calc2(sz[u], mid + 1)) { end = mid-1; if(calc2(sz[u], mid) < calc2(sz[u], best)) best = mid; } else { ini = mid + 2; if(calc2(sz[u], mid+1) < calc2(sz[u], best)) best = mid+1; } } auto it2 = b.upper_bound(best); if(it2 != b.end()) ans = min(ans, calc2(sz[u], *it)); if(it2 != b.begin()) { it2--; ans = min(ans, calc2(sz[u], *it)); } } a.insert(sz[u]); for(int &i : g[u]) if(i != p) dfs(i, u); a.erase(sz[u]); b.insert(sz[u]); } int32_t main() { cin >> n; for(int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; g[a].pb(b); g[b].pb(a); } get(1, 1); dfs(1, 1); cout << ans << endl; }

Compilation message (stderr)

papricice.cpp: In function 'void setIO(std::string)':
papricice.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
papricice.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   28 |   freopen((s+".out").c_str( ),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...