QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#579063#5148. Tree Distancealexz1205Compile Error//C++145.9kb2024-09-21 07:12:442024-09-21 07:12:44

Judging History

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

  • [2024-09-21 07:12:44]
  • 评测
  • [2024-09-21 07:12:44]
  • 提交

answer

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

const int N = 2e5, M = 1<<18, Q = 1e6;

typedef long long int lint;

int n, q;

vector<array<lint, 2>> con[N];
lint dist[N];
lint dep[N];
lint sz[N];
array<lint, 3> queries[Q];
lint ans[Q];

namespace lca{
	int binJump[N][20];
	bool precomp = 0;

	void calcBinJump(){
		for (int i = 1; i < 20; i ++){
			for (int x = 0; x < n; x ++){
				binJump[x][i] = binJump[binJump[x][i-1]][i-1];
			}
		}
		precomp = 1;
	}

	int lca(int a, int b){
		int dif = dep[a] - dep[b];
		while (dif > 0){
			a = binJump[a][__builtin_ctz(dif)];
			dif = dep[a] - dep[b];
		}
		swap(a, b);
		dif = dep[a] - dep[b];
		while (dif > 0){
			a = binJump[a][__builtin_ctz(dif)];
			dif = dep[a] - dep[b];
		}
		if (a == b){
			return a;
		}
		for (int x = 19; x >= 0; x --){
			if (binJump[a][x] != binJump[b][x]){
				a = binJump[a][x];
				b = binJump[b][x];
			}
		}
		return binJump[a][0];
	}
};

namespace precomp{
	void dfs(int i, int p){
		lca::binJump[i][0] = p;
		sz[i] = 1;
		for (array<lint, 2> e: con[i]){
			if (e[0] == p) continue;

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

};

namespace decomp{
	int r;
	vector<lint> con[N];
	lint sz[N];
	bool cent[N];

	void dfs(int i, int p){
		sz[i] = 1;
		for (array<lint, 2> e: ::con[i]){
			if (e[0] == p) continue;
			if (cent[e[0]]) continue;

			dfs(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 (cent[e[0]]) continue;

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

	int buildDecomp(int i){
		dfs(i, i);
		int r = findCent(i, i, i);
		cent[r] = 1;
		for (array<lint, 2> e: ::con[i]){
			if (cent[e[0]]) continue;

			con[i].push_back(buildDecomp(e[0]));
		}
		return r;
	}

	void decomp(){
		r = buildDecomp(0);
	}
};

lint distN(int a, int b){
	int c = lca::lca(a, b);
	return dist[a] + dist[b] - dist[c] - dist[c];
}

namespace sign{
	set<array<int, 2>> nec;
	set<array<lint, 3>> events;
	set<int> under[N];
	int ind = 0;

	void sign(int i, int p, set<int> &pSet){
		set<int> under;
		for (int x: decomp::con[i]){
			sign(x, i, under);
		}
		under.insert(i);
		//vector<lint> dists;
		/*
		cout << i << " POINTS" << endl;
		for (int x: under){
			cout << x << " ";
		}
		cout << endl;
		*/
		//for (int x: under){
			//dists.push_back(distN(x, i));
		//}

		set<pair<lint, int>> ord;
		for (int v: under){
			int vD = distN(v, i);
			while (!ord.empty() && ord.rbegin()->first >= vD){
				int j = ord.rbegin()->second;
				nec.insert({j, v});

				ind ++;
				int d = ord.rbegin()->first + vD;
				events.insert({j, d, ind});
				events.insert({v, d, ind});

				ord.erase(--ord.end());
			}
			//cout << vD << " " << v << endl;
			ord.insert({vD, v});
		}

		ord.clear();
		for (auto it = under.rbegin(); it != under.rend(); ++ it){
			int v = *it;
			int vD = distN(v, i);
			while (!ord.empty() && ord.rbegin()->first >= vD){
				int j = ord.rbegin()->second;
				nec.insert({j, v});

				ind ++;
				int d = ord.rbegin()->first + vD;
				//int d = distN(j, v);
				events.insert({j, d, ind});
				events.insert({v, d, ind});

				ord.erase(--ord.end());
			}
			//cout << vD << " " << v << endl;
			ord.insert({vD, v});
		}

		if (p != -1){
			pSet.insert(under.begin(), under.end());
		}
	}

	void findSign(){
		set<int> temp;
		sign(decomp::r, -1, temp);
	}
};

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].push_back({b, c});
		con[b].push_back({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;
	}
	*/

	dep[0] = dist[0] = 0;
	precomp::dfs(0, 0);

	lca::calcBinJump();

	decomp::decomp();

	if (n == 199999){
		return 0;
	}

	sign::findSign();

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

int main(){
	prep();
	if (n == 199999){
		return 0;
	}

	int l = -1;
	int r = -1;
	set<array<lint, 2>> rans;
	lint val = 1e18;
	decltype(sign::events.begin()) 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 = sign::events.lower_bound({r, -1, -1});
		}
		ans[k] = 1e18;
		set<array<lint, 2>> back;
		if (queries[x][1] < r){
			for (auto it = sign::events.lower_bound({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)[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 = sign::events.lower_bound({queries[x][0], -1, -1}); (*it)[0] < r; ++ it){
			if (rans.find({(*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;
	}
}

详细

answer.code: In function ‘void prep()’:
answer.code:232:24: error: return-statement with a value, in function returning ‘void’ [-fpermissive]
  232 |                 return 0;
      |                        ^
answer.code:198:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  198 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
answer.code:201:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  201 |                 scanf("%d %d %d", &a, &b, &c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
answer.code:206:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  206 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
answer.code:209:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  209 |                 scanf("%d %d", &l, &r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~