QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#563514#5148. Tree DistancesynonymML 0ms0kbC++173.7kb2024-09-14 13:24:262024-09-14 13:24:26

Judging History

你现在查看的是最新测评结果

  • [2024-09-14 13:24:26]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-09-14 13:24:26]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int mxn = 2e5+5;

int n;
vector<array<int,2>> adj[mxn];

//centroid
int vis[mxn];
vector<array<int,2>> dist[mxn];

int dfs_size(int v, int p) {
	if (vis[v]) return 0;
	int su = 1;
	for (auto [u,d] : adj[v]) {
		if (u==p) continue;
		su += dfs_size(u,v);
	}
	return su;
}
int dfs_dist(int v, int p, int dt, int o) {
	if (vis[v]) return 0;
	dist[o].push_back({v,dt});
	for (auto [u,d] : adj[v]) {
		if (u==p) continue;
		dfs_dist(u,v,dt+d,o);
	}
}
int centroid(int v, int p, int sub) {
	//check if v is valid
	int ok = 1;
	for (auto [u,d] : adj[v]) {
		if (dfs_size(u,v)*2 > sub) {
			ok=0;
			break;
		}
	}
	if (!ok) {
		for (auto [u,d] : adj[v]) {
			if (u==p) continue;
			if (vis[u]) continue;
			if (centroid(u,v,sub)) return 1;
		}
		assert(0);
		return 0;
	} else {
		dfs_dist(v,v,0,v);
		vis[v] = 1;
		for (auto [u,d] : adj[v]) {
			if (vis[u]) continue;
			int k = dfs_size(u,u);
			centroid(u,u,k);
		}
		return 1;
	}
}

struct RMQ {
	int INF = 1e16;
	int len = 1;
	vector<int> segmx;
	RMQ() {}
	RMQ(int l) {
		while (len < l) len *= 2;
		segmx = vector<int>(2*len,INF);
	}
	RMQ(vector<int> arr) {
		while (len < sz(arr)) len *= 2;
		segmx = vector<int>(2*len,INF);
		for (int i = 0; i < sz(arr); i++) {segmx[len+i] = arr[i];}
		for (int i = len-1; i > 0; i--) {
			segmx[i] = min(segmx[2*i], segmx[2*i+1]);
		}
	}
	void set(int ind, int val) {
		assert(0 <= ind && ind < len);
		ind += len; segmx[ind] = val;
		while (ind /= 2) {segmx[ind] = min(segmx[2*ind], segmx[2*ind+1]);}
	}
	int rangemin(int l, int r) {
		int res = INF; r++;
		for (l += len, r += len; l < r; l /= 2, r /= 2) {
			if (l&1) res = min(res, segmx[l++]);
		    if (r&1) res = min(res, segmx[--r]);
		}
		return res;
	}
};

vector<array<int,3>> rg;
int q;
array<int,3> qry[mxn*5];
RMQ rr;
int ans[mxn];

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n;
	for (int i=1; i<n; i++) {
		int u,v,w; cin>>u>>v>>w; --u; --v;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	
	centroid(0,0,n);
	
	for (int X=0; X<n; X++) {
		sort(all(dist[X]));
//		cout<<X<<":\n";
//		for (auto [a,b] : dist[X]) cout<<a<<","<<b<<"  ";
//		cout<<endl;
		stack<array<int,2>> mono;
		//forward
		for (int i=0; i<sz(dist[X]); i++) {
			while (sz(mono) && mono.top()[1] > dist[X][i][1]) {mono.pop();}
			if (sz(mono)) {
				rg.push_back({mono.top()[0],dist[X][i][0],mono.top()[1]+dist[X][i][1]});
//				if (i<mono.top()[0]) cout<<i<<endl;
			}
			mono.push(dist[X][i]);
		}
		while (sz(mono)) mono.pop();
		for (int i=sz(dist[X])-1; i>=0; i--) {
			while (sz(mono) && mono.top()[1] > dist[X][i][1]) {mono.pop();}
			if (sz(mono)) {
				rg.push_back({dist[X][i][0],mono.top()[0],mono.top()[1]+dist[X][i][1]});
//				if (i>mono.top()[0]) cout<<i<<endl;
			}
			mono.push(dist[X][i]);
		}
	}
	rr = RMQ(n);
	sort(all(rg)); reverse(all(rg));
	int q; cin>>q;
	for (int i=0; i<q; i++) {
		cin>>qry[i][0]>>qry[i][1]; --qry[i][0], --qry[i][1];
		qry[i][2] = i;
	}
//	for (auto [a,b,c] : rg) {
//		cout<<a+1<<" "<<b+1<<" "<<c<<endl;
//	}
//	return 0;
	sort(qry,qry+q);
	reverse(qry,qry+q);
	int rp = 0, qp = 0;
	for (int i=n-1; i>=0; i--) {
		while (rp < sz(rg) && rg[rp][0]==i) {
			int pp = rg[rp][1];
			int vv = rr.rangemin(pp,pp);
			rr.set(pp,min(vv,rg[rp][2]));
			rp++;
		}
		while (qp < q && qry[qp][0]==i) {
			ans[qry[qp][2]] = rr.rangemin(i,qry[qp][1]);
			qp++;
		}
	}
	for (int i=0; i<q; i++) {
		cout<<(ans[i]>1e15?-1:ans[i])<<"\n";
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Memory Limit Exceeded

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: