Submission #366476

#TimeUsernameProblemLanguageResultExecution timeMemory
366476ne4eHbKaPapričice (COCI20_papricice)C++17
50 / 110
372 ms45932 KiB
#include <bits/stdc++.h> using namespace std; #ifndef _LOCAL //#pragma GCC optimize("O3,Ofast") #else #pragma GCC optimize("O0") #endif template<typename t> inline void umin(t &a, const t b) {a = min(a, b);} template<typename t> inline void umax(t &a, const t b) {a = max(a, b);} typedef long long ll; #define int ll typedef pair<int, int> pii; typedef long double ld; ll time() {return chrono::system_clock().now().time_since_epoch().count();} mt19937 rnd(time()); #define ft first #define sd second #define len(f) int((f).size()) #define bnd(f) (f).begin(), (f).end() #define _ <<' '<< const int inf = 1e9 + 5; const ll inf64 = 4e18 + 5; const int md = 998244353; namespace MD { void add(int &a, const int b) {if((a += b) >= md) a -= md;} void sub(int &a, const int b) {if((a -= b) < 0) a += md;} int prod(const int a, const int b) {return ll(a) * b % md;} }; const int N = 4e5 + 5; int n; list<int> g[N]; int tin[N], tout[N], timer, si[N]; struct tree { tree *l{}, *r{}; pii v{+inf, -inf}; tree(int tl = 0, int tr = n) { if(tl < tr) { int tm = tl + tr >> 1; l = new tree(tl, tm); r = new tree(tm + 1, tr); } } void add(int u, int tl = 0, int tr = n) { umin(v.ft, tout[u]); umax(v.sd, tin[u]); if(tl == tr) return; int tm = tl + tr >> 1; si[u] <= tm ? l->add(u, tl, tm) : r->add(u, tm + 1, tr); } pii get(int L, int R, int tl = 0, int tr = n) { if(L > R) return {+inf, -inf}; if(L == tl && R == tr) return v; int tm = tl + tr >> 1; pii le = l->get(L, min(R, tm), tl, tm); ++tm; pii ri = r->get(max(tm, L), R, tm, tr); return {min(le.ft, ri.ft), max(le.sd, ri.sd)}; } } *t; void init(int v = 0, int pr = -1) { tin[v] = timer++; si[v] = 1; g[v].remove(pr); for(int u : g[v]) init(u, v), si[v] += si[u]; tout[v] = timer++; } set<int> f, fg; int dfs(int v = 0) { int a = si[v]; int res = +inf; if(!f.empty()) { auto it = f.lower_bound(a + (n - a + 1 >> 1)); if(it != f.end()) { int b = *it - a; int c = n - a - b; if(b > c) swap(b, c); umin(res, max(abs(b - c), max( abs(a - b), abs(a - c)))); } } if(!fg.empty()) { auto it2 = fg.lower_bound(n - a + 1 >> 1); if(it2 != fg.end()) { int b = *it2; int c = n - a - b; umin(res, max(abs(b - c), max( abs(a - b), abs(a - c)))); } } if(!g[v].empty()) { f.insert(a); fg.insert(n - a); for(int u : g[v]) umin(res, dfs(u)); f.erase(a); fg.erase(n - a); } return res; } bool works(int d) { for(int i = 0; i < n; ++i) { int a = si[i]; if(a * 3 > n) continue; if(a * 3 + d * 2 < n) continue; pii z = t->get(max(a, n - a - a - d), min(n - a - a, a + d)); if(z.ft < tin[i] || z.sd > tout[i]) return true; } return false; } void solve() { cin >> n; for(int i = 1; i < n; ++i) { int x, y; cin >> x >> y; --x, --y; g[x].push_back(y); g[y].push_back(x); } init(); t = new tree(); for(int i = 0; i < n; ++i) t->add(i); int l = 0, r = dfs(); while(l < r) { int m = l + r >> 1; works(m) ? r = m : l = m + 1; } cout << l << endl; #ifdef KEK timer = 0; for(int i = 0; i < n; ++i) g[i].clear(); f.clear(); fg.clear(); #endif // KEK } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef _LOCAL // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); #else system("color a"); freopen("in.txt", "r", stdin); int t; cin >> t; while(t--) #endif solve(); }

Compilation message (stderr)

papricice.cpp: In constructor 'tree::tree(ll, ll)':
papricice.cpp:40:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
papricice.cpp: In member function 'void tree::add(ll, ll, ll)':
papricice.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
papricice.cpp: In member function 'pii tree::get(ll, ll, ll, ll)':
papricice.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
papricice.cpp: In function 'll dfs(ll)':
papricice.cpp:80:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         auto it = f.lower_bound(a + (n - a + 1 >> 1));
      |                                      ~~~~~~^~~
papricice.cpp:91:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         auto it2 = fg.lower_bound(n - a + 1 >> 1);
      |                                   ~~~~~~^~~
papricice.cpp: In function 'void solve()':
papricice.cpp:138:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |         int m = l + r >> 1;
      |                 ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...