QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#584024#5148. Tree Distancealexz1205WA 0ms18712kbC++174.7kb2024-09-23 04:23:152024-09-23 04:23:16

Judging History

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

  • [2024-09-23 04:23:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:18712kb
  • [2024-09-23 04:23:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5, Q = 1e6;

typedef long long int lint;

int n, q;

set<array<lint, 2>> con[N];
array<lint, 3> queries[Q];
lint ans[Q];

namespace decomp{
	int ind2 = 0;
	array<lint, 3> events[(int)8e6];
	//vector<array<lint, 3>> events;

	lint sz[N];
	lint dist[N];
	vector<int> cur;
	int ind = 0;
	vector<array<lint, 2>> ord;

	void dfs(int i, int p){
		sz[i] = 1;
		for (auto it = ::con[i].begin(); it != ::con[i].end(); ++ it){
			const array<lint, 2> &e = *it;
			if (e[0] == p){
				continue;
			}

			dfs(e[0], i);
			sz[i] += sz[e[0]];
		}
	}

	void dat(int i, int p){
		cur.push_back(i);
		sz[i] = 1;
		for (auto it = ::con[i].begin(); it != ::con[i].end(); ++ it){
			const array<lint, 2> &e = *it;
			if (e[0] == p){
				continue;
			}

			dist[e[0]] = dist[i] + e[1];
			dat(e[0], i);
			sz[i] += sz[e[0]];
		}
	}

	int findCent(int i, int p, int s){
		for (array<lint, 2> e: ::con[i]){
			if (e[0] == p) continue;

			if (sz[e[0]] >= sz[s]/2){
				return findCent(e[0], i, s);
			}
		}
		return i;
	}

	void buildDecomp(int i){
		dfs(i, i);
		int r = findCent(i, i, i);
		dist[r] = 0;
		cur.clear();
		dat(r, r);
		sort(cur.begin(), cur.end());

		ord.clear();
		for (int v: cur){
			lint vD = dist[v];
			while (!ord.empty() && ord.back()[0] >= vD){
				int j = ord.back()[1];

				ind ++;
				lint d = ord.back()[0] + vD;
				//events.push_back({j, d, ind});
				//events.push_back({v, d, ind});
				events[ind2++] = {j, d, ind};
				events[ind2++] = {v, d, ind};

				ord.pop_back();
			}
			ord.push_back({vD, v});
		}

		ord.clear();
		for (int x = cur.size()-1; x >= 0; x --){
			int v = cur[x];
			lint vD = dist[v];
			while (!ord.empty() && ord.back()[0] >= vD){
				int j = ord.back()[1];

				ind ++;
				lint d = ord.back()[0] + vD;
				//events.push_back({j, d, ind});
				//events.push_back({v, d, ind});
				events[ind2++] = {j, d, ind};
				events[ind2++] = {v, d, ind};

				ord.pop_back();
			}
			ord.push_back({vD, v});
		}
		for (array<lint, 2> e: ::con[r]){
			::con[e[0]].erase({r, e[1]});
			buildDecomp(e[0]);
		}
	}

	void decomp(){
		buildDecomp(0);
		//BigThing b;
		//b.buildDecomp(0);
	}
};

int B;

void prep(){
	scanf("%d", &n);
	for (int x = 1; x < n; x ++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		a --, b --;
		con[a].insert({b, c});
		con[b].insert({a, c});
	}
	scanf("%d", &q);
	for (int x = 0; x < q; x ++){
		int l, r;
		scanf("%d %d", &l, &r);
		l --, r --;
		queries[x][0] = l;
		queries[x][1] = r;
		queries[x][2] = x;
	}
	B = n/(int)sqrt(n);

	sort(queries, queries + q, [](array<lint, 3> a, array<lint, 3> b){return (array<lint, 2>){a[0]/B, a[1]} < (array<lint, 2>){b[0]/B, b[1]};});
	/*
	for (int x = 0; x < q; x ++){
		cout << queries[x][0] << " " << queries[x][1] << " " << queries[x][2] << endl;
	}
	*/

	decomp::decomp();

	sort(decomp::events, decomp::events + decomp::ind2);
	//sort(decomp::events.begin(), decomp::events.end());

	if (n == 199999) exit(0);

	/*
	for (array<lint, 3> p : decomp::events){
		cout << p[0] << " " << p[1] << " " << p[2] << endl;
	}
	*/
}

int main(){
	cout << "START" << endl;
	prep();

	int l = -1;
	int r = -1;
	set<array<lint, 2>> rans;
	lint val = 1e18;
	using namespace decomp;
	auto beg = events, end = events+ind2;
	//auto beg = events.begin(), end = events.end();
	decltype(beg) at;
	for (int x = 0; x < n; x ++){
		int k = queries[x][2];
		if ((queries[x][0]/B)*B != l){
			rans.clear();
			val = 1e18;
			l = (queries[x][0]/B) * B;
			r = l + B;
			//at = events.lower_bound((array<lint, 2>){r, -1, -1});
			at = lower_bound(beg, end, (array<lint, 3>){r, -1, -1});
		}
		//ans[k] = val;
		ans[k] = 1e18;
		set<array<lint, 2>> back;
		if (queries[x][1] < r){
			for (auto it = lower_bound(beg, end, (array<lint, 3>){queries[x][0], -1, -1}); (*it)[0] <= queries[x][1]; ++ it){
				if (!back.insert({(*it)[2], (*it)[1]}).second){
					ans[k] = min(ans[k], (*it)[1]);
					continue;
				}
			}
			continue;
		}
		while (at != end && (*at)[0] <= queries[x][1]){
			if (!rans.insert({(*at)[2], (*at)[1]}).second){
				val = min(val, (*at)[1]);
				at ++;
				continue;
			}
			at ++;
		}
		ans[k] = val;
		for (auto it = lower_bound(beg, end, (array<lint, 3>){queries[x][0], -1, -1}); (*it)[0] < r; ++ it){
			if (rans.find((array<lint, 2>){(*it)[2], (*it)[1]}) != rans.end()){
				ans[k] = min(ans[k], (*it)[1]);
				continue;
			}
			if (!back.insert({(*it)[2], (*it)[1]}).second){
				ans[k] = min(ans[k], (*it)[1]);
				continue;
			}
		}
	}
	for (int x = 0; x < q; x ++){
		if (ans[x] == 1e18) {
			cout << -1 << endl;
			continue;
		}
		cout << ans[x] << endl;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 18712kb

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:

START
-1
3
7
7
2

result:

wrong output format Expected integer, but "START" found