QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#570016#5148. Tree DistanceaaaaaRE 0ms0kbC++202.4kb2024-09-17 13:15:492024-09-17 13:15:51

Judging History

This is the latest submission verdict.

  • [2024-09-17 13:15:51]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-09-17 13:15:49]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=300010,M=1000010;
ll n,tot,first[N],nnext[N<<1],to[N<<1],w[N<<1],siz[N],f[N],root,s,a[N],cnt,vis[N],cntd;
ll dis[N],pp[N],ans[M];
set<ll>ss;
// vector<pair<ll,ll> >p[N];
unordered_map<ll, vector<pair<ll, ll>>> p;
struct sss {
	ll x,y;
	ll v;
	bool operator<(sss b) {
		return x<b.x;
	}
} d[M*8];
void add(ll x,ll y,ll z) {
	nnext[++tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	w[tot]=z;
}
void getroot(ll u,ll fa) {
	siz[u]=1;
	f[u]=0;
	for(ll e=first[u]; e; e=nnext[e]) {
		if(!vis[to[e]]&&to[e]!=fa) {
			getroot(to[e],u);
			siz[u]+=siz[to[e]];
			f[u]=max(f[u],siz[to[e]]);
		}
	}
	f[u]=max(f[u],s-siz[u]);
	if(f[u]<f[root]) {
		root=u;
	}
}
void getdep(ll u,ll fa) {
	a[++cnt]=u;
	for(ll e=first[u]; e; e=nnext[e]) {
		if(!vis[to[e]]&&to[e]!=fa) {
			dis[to[e]]=dis[u]+w[e];
			getdep(to[e],u);
		}
	}
}
void dfs(ll u) {
	dis[u]=cnt=0;
	vis[u]=1;
	getdep(u,0);
	sort(a+1,a+cnt+1,[](ll a,ll b) {
		return dis[a]<dis[b];
	});
	ss.clear();
	for(ll i=1; i<=cnt; i++) {
		ss.insert(a[i]);
		auto pos=ss.find(a[i]);
		if(pos!=ss.begin()) {
			pos--;
			d[++cntd]= {*pos,a[i],dis[*pos]+dis[a[i]]};
			pos++;
		}
		pos++;
		if(pos!=ss.end()) {
			d[++cntd]= {*pos,a[i],dis[*pos]+dis[a[i]]};
		}
	}
	for(ll e=first[u]; e; e=nnext[e]) {
		if(!vis[to[e]]) {
			root=0;
			s=siz[to[e]];
			getroot(to[e],u);
			dfs(root);
		}
	}
}
inline ll lowbit(ll x) {
	return x&(-x);
}
inline void update(ll x,ll y) {
	while(x<=n) {
		pp[x]=min(pp[x],y);
		x+=lowbit(x);
	}
}
inline ll query(ll x) {
	ll ans=1e18;
	while(x>=1) {
		ans=min(ans,pp[x]);
		x-=lowbit(x);
	}
	return ans;
}
int main() {
	ll now,a,b,c,q;
	scanf("%d",&n);
	for(ll i=1; i<=n-1; i++) {
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	f[0]=1e18;
	s=n;
	getroot(1,0);
	dfs(root);
	for(ll i=1; i<=cntd; i++) {
		if(d[i].x>d[i].y) {
			swap(d[i].x,d[i].y);
		}
	}
	sort(d+1,d+cntd+1);
	now=cntd;
	scanf("%d",&q);
	for(ll i=1; i<=q; i++) {
		scanf("%d%d",&a,&b);
		if(a>=b) {
			ans[i]=-1;
			continue;
		}
		p[a].push_back({b,i});
	}
	memset(pp,127,sizeof(pp));
	for(ll i=n; i>=1; i--) {
		while(d[now].x>=i) {
			update(d[now].y,d[now].v);
			now--;
		}
		for(auto j:p[i]) {
			ans[j.second]=query(j.first);
		}
	}
	for(ll i=1; i<=q; i++) {
		printf("%lld\n",ans[i]);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5
1 2 5
1 3 3
1 4 4
3 5 2
5
1 1
1 4
2 4
3 4
2 5

output:


result: