Submission #970793

#	Time	Username	Problem	Language	Result	Execution time	Memory
970793		Tozzyyyy	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	3951 ms	60100 KiB

meetings2

#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;
#define int long long
const int inf = 1e18+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(long long int, long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int mid = l + r >> 1;
      |             ~~^~~
meetings2.cpp: In member function 'long long int segment_tree::get(long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid = l + r >>1;
      |             ~~^~~
meetings2.cpp: In member function 'void segment_tree_2::update(long long int, long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid = l + r >> 1;
      |             ~~^~~
meetings2.cpp: In member function 'void segment_tree_2::reset(long long int, long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int mid = l + r >> 1;
      |             ~~^~~
meetings2.cpp: In member function 'long long int segment_tree_2::get(long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:82:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |   int mid = l + r >>1;
      |             ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80