mxqz 二分+点分治 TLE on #22
查看原帖
mxqz 二分+点分治 TLE on #22
317459
RyexAwl新暗车楼主2021/12/16 12:51
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target ("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <bits/stdc++.h>
 
#define rep(i,l,r) for (int i = l; i <= r; i++)
#define per(i,r,l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define prt std::cout
#define gin std::cin
#define edl std::endl
 
namespace wxy{
 
const int N = 5e5+50;
 
int head[N],edge[N<<1],fail[N<<1],w[N<<1],tot;
 
int size[N],sz,rt,n;
 
int PreDepDist[N],DepDist[N],dist[N],dep[N],Mx[N],val[N];
 
int max_part[N],p[N],res,s,check,t;
 
int root;
 
int loc[N];
 
int l,r;
 
int LongDep[N],pos[N];
 
int Mx_dep,G[N];
 
bool vis[N];
 
inline void add(int x,int y,int we) {
	edge[++tot] = y;
	fail[tot] = head[x];
	w[tot] = we;
	head[x] = tot;
}
 
inline void calc_size(int x,int fa) {
	size[x] = 1; max_part[x] = 0;
	for(int i = head[x]; i; i = fail[i]) {
		int v = edge[i];
		if (vis[v] || v == fa) continue;
		calc_size(v,x); size[x] += size[v];
		max_part[x] = std::max(max_part[x],size[v]);
	}
	max_part[x] = std::max(max_part[x],sz - size[x]);
	if (2 * max_part[x] <= sz && !rt) rt = x; 
}
 
inline void calc_dist(int x,int fa) {
	if (DepDist[dep[x]] < dist[x]) {
		DepDist[dep[x]] = std::max(DepDist[dep[x]],dist[x]);
		loc[dep[x]] = x;
	}
	Mx_dep = std::max(dep[x],Mx_dep);
	for (int i = head[x]; i; i = fail[i]) {
		int v = edge[i];
		if (v == fa || vis[v]) continue;
		dist[v] = dist[x] + (w[i]>=check?1:-1);
		dep[v] = dep[x] + 1;
		calc_dist(v,x);
	}
}
 
int edge_w[N]; 
 
inline void dfs(int x,int fa) {
	int cnt = 0; vis[x] = true;
	for (int i = head[x]; i; i = fail[i]) {
		int v = edge[i];
		if (vis[v] || v == fa) continue;
		Mx_dep = 0; p[++cnt] = v; dep[v] = 1; edge_w[v] = w[i];
		dist[v] = (w[i]>=check?1:-1);
		calc_dist(v,x); LongDep[v] = Mx_dep;
		rep(j,1,LongDep[v]) DepDist[j] = 0xcfcfcfcf;
	}
	std::sort(p+1,p+1+cnt,[](int x,int y){return LongDep[x] < LongDep[y];});
	int pre = 0; 
	PreDepDist[0] = 0; pos[0] = x; 
	rep(i,1,cnt) {
		int v = p[i];
		dep[v] = 1; dist[v] = (edge_w[v]>=check?1:-1); calc_dist(v,x); 
		std::deque<int> q;
		per(j,pre,0) {
			while (q.size() && q.front() - j > r - l) q.pop_back();
			while (q.size() && PreDepDist[q.back()] <= PreDepDist[j]) q.pop_back();
			q.push_back(j);
			Mx[j] = q.front();
		}
		rep(j,0,pre) if (l - j >= 1) val[l - j] = Mx[j]; 
		rep(j,1,LongDep[v]) {
			if (val[j] < 0) continue;
			int Val = PreDepDist[val[j]] + DepDist[j];
			if (Val > res) {
				res = Val; 
				s = pos[val[j]];
				t = loc[j];
			} 
		}
		rep(j,1,pre) Mx[j] =  0xcfcfcfcf;
		rep(j,1,LongDep[v]) {
			if (PreDepDist[j] < DepDist[j]) {
				PreDepDist[j] = std::max(PreDepDist[j],DepDist[j]);
				pos[j] = loc[j];
			}
		} 
		rep(j,1,LongDep[v]) DepDist[j] = 0xcfcfcfcf;
		rep(j,0,pre) if (l - j >= 1) val[l - j] = 0xcfcfcfcf;
		pre = LongDep[v];
	} rep(j,0,pre) PreDepDist[j] = 0xcfcfcfcf;
	for (int i = head[x]; i; i = fail[i]) {
		int v = edge[i]; 
		if (vis[v] || v == fa) continue;
		dfs(G[v],-1);
	}
}

void init(int x,int fa){
	vis[x] = true;
	for (int i = head[x]; i; i = fail[i]) {
		int v = edge[i];
		if (vis[v] || v == fa) continue;
		sz = size[v]; rt = 0; calc_size(v,x); 
		G[v] = rt;
		calc_size(rt,-1); init(rt,-1);
	}
}
 
inline int read(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
    return s*f;
}

int Mx_edge;
 
void solve(){
	int l = 0,r = 32767; 
	memset(vis,false,sizeof vis); calc_size(root,-1); init(root,-1);
	memset(val,0xcf,sizeof val);
	memset(DepDist,0xcf,sizeof DepDist);
	memset(PreDepDist,0xcf,sizeof PreDepDist); 
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		memset(vis,false,sizeof vis);
		check = mid; rt = root; 
		res = 0xcfcfcfcf; dfs(rt,-1); 
		if (res >= 0) l = mid;
		else r = mid - 1;
	} 
	memset(vis,false,sizeof vis);
	check = l; rt = root; 
	res = 0xcfcfcfcf; dfs(rt,-1); 
	prt << s << " " << t;
}
 
inline void main(){
    #ifndef ONLINE_JUDGE
        freopen("in.in","r",stdin);
        freopen("out.out","w",stdout);
    #endif
    n = read(); l = read(); r = read();
    rep(i,1,n-1) {
		int a,b,c; a = read(); b = read(); c = read();
		add(a,b,c); add(b,a,c); Mx_edge = std::max(Mx_edge,c);
	} 
	sz = n; calc_size(1,-1); root = rt; solve();
}
 
}signed main(){wxy::main(); return 0;}
2021/12/16 12:51
加载中...