Submission #970797

#TimeUsernameProblemLanguageResultExecution timeMemory
970797TozzyyyyMeetings 2 (JOI21_meetings2)C++17
100 / 100
3624 ms41408 KiB
#include<bits/stdc++.h> #define pll pair<long long, long long> #define fi first #define se second #define bit(i,j) ((j >> i) & 1) using namespace std; const long long inf = 1e9+1; const int mod = 1e9+7; const int MAXN = 2e5+100; vector<int> adj[MAXN]; int sz[MAXN] , del[MAXN]; int get_size(int u , int p){ sz[u] = 1; for(auto v : adj[u]) if(v!=p and !del[v]) sz[u] += get_size(v , u); return sz[u]; } int get_cen(int u , int p , int n){ for(auto v : adj[u]) if(v!=p and !del[v] and sz[v] > n/2) return get_cen(v , u , n); return u; } struct segment_tree{ int t[4 * MAXN]; int d[4 * MAXN]; void push(int id , int l , int r){ if(l == r) return; if(d[id] == -inf) return; d[id<<1] = max(d[id<<1] , d[id]) ; d[id<<1|1] = max(d[id<<1|1] , d[id]); t[id<<1] = max(t[id<<1] , d[id]) ; t[id<<1|1] = max(t[id<<1|1] , d[id]); d[id] = -inf; } void update(int id , int l, int r , int x , int y , int val){ push(id , l , r); if(r < x or l > y) return ; if(l >= x and r <= y){ t[id] = max(t[id] , val) ; d[id] = max(d[id] , val) ; return; } int mid = l + r >> 1; update(id<<1 , l , mid , x , y , val); update(id<<1|1 , mid+1 , r , x , y , val); t[id] = max(t[id<<1] , t[id<<1|1]); } int get(int id , int l , int r , int x , int y){ push(id, l , r); if(r < x or l > y) return -inf; if(l >= x and r <= y) return t[id]; int mid = l + r >>1; return max(get(id<<1 , l , mid , x , y) , get(id<<1|1 , mid+1 , r , x , y)); } } ans; struct segment_tree_2{ int t[4 * MAXN]; void update(int id , int l, int r , int x , int y , int val){ if(r < x or l > y) return ; if(l >= x and r <= y){ t[id] = max(t[id] , val); return; } int mid = l + r >> 1; update(id<<1 , l , mid , x , y , val); update(id<<1|1 , mid+1 , r , x , y , val); t[id] = max(t[id<<1] , t[id<<1|1]); } void reset(int id , int l, int r , int x , int y , int val){ if(r < x or l > y) return ; if(l >= x and r <= y){ t[id] = val; return; } int mid = l + r >> 1; reset(id<<1 , l , mid , x , y , val); reset(id<<1|1 , mid+1 , r , x , y , val); t[id] = max(t[id<<1] , t[id<<1|1]); } int get(int id , int l , int r , int x , int y){ if(r < x or l > y) return -inf; if(l >= x and r <= y) return t[id]; int mid = l + r >>1; return max(get(id<<1 , l , mid , x , y) , get(id<<1|1 , mid+1 , r , x , y)); } } T; int mp[MAXN]; vector<pll> s; int n; vector<int> vt; void dfs(int u , int p , int d){ int mx = T.get(1 , 1 , n , sz[u] , n); if(mx != -inf) ans.update(1 , 1 , n , 2 , sz[u] * 2 , mx + d + 1); for(auto v : adj[u]){ if(del[v] == 0 and v != p) dfs(v , u , d+1); } s.push_back({sz[u] , d}); vt.push_back(sz[u]); } void solve(int u){ u = get_cen(u , 0 , get_size(u , 0)); del[u] = 1; get_size(u , u); for(auto v : adj[u]){ if(del[v] == 1) continue; T.update(1 , 1 , n , sz[u] - sz[v] , sz[u]-sz[v] , 0) ; vt.push_back(sz[u] - sz[v]) , dfs(v , u , 1); for(auto x : s) T.update(1 , 1 , n , x.fi , x.fi , x.se); s.clear(); } for(auto x : vt) T.reset(1 , 1 , n , x , x , -inf); vt.clear(); for(int v , j = adj[u].size() - 1 ; j >= 0 ; j--){ v = adj[u][j]; if(del[v] == 1) continue; T.update(1 , 1 , n , sz[u] - sz[v] , sz[u]-sz[v] , 0) ; vt.push_back(sz[u] - sz[v]) , dfs(v , u , 1); for(auto x : s) T.update(1 , 1 , n , x.fi , x.fi , x.se); s.clear(); } for(auto x : vt) T.reset(1 , 1 , n , x , x , -inf); vt.clear(); for(auto v : adj[u]){ if(del[v] == 1) continue; solve(v); } } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); for(int i = 0 ; i < 4 * MAXN; i++) T.t[i] = -inf, ans.t[i] = 1 , ans.d[i] = -inf; cin >> n; for(int i = 1 ; i < n ; i++){ int x , y; cin >> x>> y; adj[x].push_back(y) ; adj[y].push_back(x); } solve(1); for(int i = 1 ; i <= n ; i++){ if(i & 1) cout << 1 << "\n"; else cout << ans.get(1 , 1 , n , i , i) << "\n"; } return 0; }

Compilation message (stderr)

meetings2.cpp: In member function 'void segment_tree::update(int, int, int, int, int, int)':
meetings2.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |   int mid = l + r >> 1;
      |             ~~^~~
meetings2.cpp: In member function 'int segment_tree::get(int, int, int, int, int)':
meetings2.cpp:51:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int mid = l + r >>1;
      |             ~~^~~
meetings2.cpp: In member function 'void segment_tree_2::update(int, int, int, int, int, int)':
meetings2.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int mid = l + r >> 1;
      |             ~~^~~
meetings2.cpp: In member function 'void segment_tree_2::reset(int, int, int, int, int, int)':
meetings2.cpp:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int mid = l + r >> 1;
      |             ~~^~~
meetings2.cpp: In member function 'int segment_tree_2::get(int, int, int, int, int)':
meetings2.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   int mid = l + r >>1;
      |             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...