Submission #386400

#	Time	Username	Problem	Language	Result	Execution time	Memory
386400		MatheusLealV	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	2467 ms	52812 KiB

meetings2

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;

// #define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
int prodmod(vector<int> w);
int summod(vector<int> w);
///CUIDADO COM MAXN
#define N 600020
int n, block[N], sz[N], qtd_vertice, pai[N];
vector<int> grafo[N];
vector<int> lista;
int paist[N], szst[N];

struct Bit{
	int bit[N];
	vector<int> limpar;
	void init(){
		for(auto x: limpar) bit[x] = -1;
		limpar.clear();
	}
	void upd(int x, int v){
		for(int i = x; i < N; i += i&(-i)){
			limpar.pb(i);
			bit[i] = max(bit[i], v);
		}
	}

	int query(int x){
		int ans=-1;
		for(int i=x;i>0;i-=i&(-i)){
			ans=max(ans, bit[i]);
		}
		return ans;
	}
} T;
void dfsst(int x, int p){
	paist[x] = p;
	szst[x]=1;
	for(auto v: grafo[x]){
		if(v==p) continue;
		dfsst(v, x);
		szst[x]+=szst[v];
	}
}
void get_size(int x, int p){
	pai[x] = p;
	lista.push_back(x);
	sz[x] = 1;
	for(auto v: grafo[x]){
		if(block[v] or v == p) continue;
		get_size(v, x);
		sz[x] += sz[v];
	}
}

int Find_Centroid(int x){
	lista.clear();
	get_size(x, x);
	qtd_vertice = sz[x];
	int centro = x;
	for(auto x: lista){
		bool ok = true;
		if(qtd_vertice - sz[x] > qtd_vertice/2) ok = false;
		for(auto v: grafo[x]){
			if(v == pai[x] or block[v]) continue;
			if(sz[v] > qtd_vertice/2) ok = false;
		}
		if(ok) centro = x;
	}

	return centro;
}

map<int, int> mapa;
int curr_sz[N], reach[N];
void dfs_sz(int x, int p){
	reach[x]=1;
	curr_sz[x] = 1;
	for(auto v: grafo[x]){
		if(v==p) continue;
		if(block[v]){
			if(v != paist[x]) curr_sz[x] += szst[v];
			else curr_sz[x] += n-szst[x];
			continue;
		}
		dfs_sz(v,x);
		curr_sz[x]+=curr_sz[v];
	}
}
int ans[N];
int total = 0;
void query(int x, int p, int dist){
	int peso = curr_sz[x]; //
	//Se a > b entao 20000 - a < 2000 - b
	// cout<<"query "<<x<<" "<<curr_sz[x]<<" "<<dist<<" "<<T.query(200002-peso)<<"\n";
	if(T.query(200002-peso) > 0) ans[2*peso] = max(ans[2*peso], 1+dist + T.query(200002-peso));
	ans[2*min(total, peso)] = max(ans[2*min(total, peso)], dist + 1);
	for(auto v: grafo[x]){
		if(v == p or block[v]) continue;
		query(v,x,dist+1);
	}
}
void upd(int x, int p, int dist){
	int peso = curr_sz[x];
	T.upd(200002-peso, dist);
	// cout<<"update "<<x<<" "<<curr_sz[x]<<" "<<dist<<"\n";
	for(auto v: grafo[x]){
		if(v==p or block[v]) continue;
		upd(v,x,dist+1);
	}
}
int solve(int x, int deep){
	x = Find_Centroid(x);
	// cout<<"CENTROID = "<<x<<"\n";
	block[x] = true;
	T.init();
	for(auto v: grafo[x]){
		if(block[v])continue;
		dfs_sz(v,x);
	}
	for(auto v: grafo[x]){
		if(block[v]) continue;
		total = n - curr_sz[v];
		query(v,x,1);
		upd(v,x,1);
	}
	T.init();
	reverse(all(grafo[x]));
	for(auto v: grafo[x]){
		if(block[v]) continue;
		total = n - curr_sz[v];
		query(v,x,1);
		upd(v,x,1);
	}
	for(auto v: grafo[x]){
		if(block[v]) continue;
		solve(v, deep+1);
	}
	return x;
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n;
	for(int i = 1, a,b;i<n;i++){
		cin>>a>>b;
		grafo[a].pb(b);
		grafo[b].pb(a);
	}
	for(int i=1;i<=n;i++) ans[i]=1;
	dfsst(1,1);
	solve(1,1);
	for(int i =N-4;i>=1;i--)ans[i]=max(ans[i],ans[i+2]);
	for(int i =1;i<=n;i++) cout<<ans[i]<<"\n";
}

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