QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334162#6111. Two PathsFISHER_WA 151ms36604kbC++144.6kb2024-02-21 11:57:332024-02-21 11:57:34

Judging History

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

  • [2024-02-21 11:57:34]
  • 评测
  • 测评结果:WA
  • 用时:151ms
  • 内存:36604kb
  • [2024-02-21 11:57:33]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define EB emplace_back
using namespace std;
typedef long long i64;
const int maxn = 200000;
int n, q;
struct edge { int v, w; };
vector<edge> g[maxn + 5];
int dep[maxn + 5];
pair<int, int> mx[maxn + 5], smx[maxn + 5], tmx[maxn + 5];
int siz[maxn + 5], son[maxn + 5];
void dfs(int u, int fa) {
	siz[u] = 1;
	for (const auto& [v, w] : g[u])
		if (v != fa) {
			dep[v] = dep[u] + w;
			dfs(v, u);
			siz[u] += siz[v];
			if (siz[v] > siz[son[u]]) son[u] = v;
			pair<int, int> nw = {mx[v].fi + w, v};
			if (nw > mx[u]) tmx[u] = smx[u], smx[u] = mx[u], mx[u] = nw;
			else if (nw > smx[u]) tmx[u] = smx[u], smx[u] = nw;
			else tmx[u] = max(tmx[u], nw);
		}
}
int tp[maxn + 5], f[maxn + 5];
int id[maxn + 5], rnk[maxn + 5], stamp;
void dfs2(int u, int fa, int t) {
	tp[u] = t, f[u] = fa;
	rnk[id[u] = ++stamp] = u;
	if (son[u]) dfs2(son[u], u, t);
	for (const auto& [v, _] : g[u])
		if (v != fa && v != son[u]) dfs2(v, u, v);
}
int mxl[maxn + 5];
void dfs3(int u, int fa) {
	for (const auto& [v, w] : g[u])
		if (v != fa) {
			mxl[v] = max(mxl[u], mx[u].se == v ? smx[u].fi : mx[u].fi) + w;
			dfs3(v, u);
		}
}
struct point {
	i64 x, y;
	bool operator<(const point& b) const { return x == b.x ? y > b.y : x < b.x; }
	point operator-(const point& b) const { return {x - b.x, y - b.y}; }
	i64 operator*(const point& b) const { return x * b.y - y * b.x; }
};
i64 mxa[4 * maxn + 5], mxb[4 * maxn + 5];
vector<point> h[4 * maxn + 5];
void build(int p, int l, int r) {
	if (l == r) {
		int u = rnk[l];
		int mxd = mx[u].se == son[u] ? smx[u].fi : mx[u].fi;
		mxa[p] = mxd - dep[u], mxb[p] = mxd + dep[u];
		return;
	}
	int mid = (l + r) / 2;
	build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
	vector<point> L = h[p << 1];
	L.insert(L.end(), h[p << 1 | 1].begin(), h[p << 1 | 1].end());
	L.PB({mxa[p << 1 | 1], mxb[p << 1]});
	sort(L.begin(), L.end());
	for (const auto& o : L) {
		while (h[p].size() > 1 && (*(h[p].end() - 1) - *(h[p].end() - 2)) * (o - *(h[p].end() - 2)) >= 0) h[p].pop_back();
		h[p].PB(o);
	}
	mxa[p] = max(mxa[p << 1], mxa[p << 1 | 1]), mxb[p] = max(mxb[p << 1], mxb[p << 1 | 1]);
}
i64 ans;
int A, B;
i64 pa;
int ea, eb;
inline void upd(i64 na, i64 nb) {
	ans = max(ans, (pa + ea) * A + (nb + eb) * B);
	pa = max(pa, na);
}
void query(int p, int l, int r, int x, int y) {
	if (x <= l && r <= y) {
		upd(mxa[p], mxb[p]);
		if (h[p].empty()) return;
		int L = 0, R = h[p].size() - 1;
		while (L < R) {
			int mid = (L + R + 1) / 2;
			if (A * h[p][mid].x + B * h[p][mid].y > A * h[p][mid - 1].x + B * h[p][mid - 1].y) L = mid;
			else R = mid - 1;
		}
		ans = max(ans, A * (h[p][L].x + ea) + B * (h[p][L].y + eb));
		return;
	}
	int mid = (l + r) / 2;
	if (mid < y) query(p << 1 | 1, mid + 1, r, x, y);
	if (mid >= x) query(p << 1, l, mid, x, y); 
}
void solve(int u, int v) {
	vector<pair<int, int>> su, sv;
	int tu = u, tv = v;
	while (tp[tu] != tp[tv]) {
		if (dep[tp[tu]] > dep[tp[tv]]) su.EB(id[tp[tu]], id[tu]), tu = f[tp[tu]];
		else sv.EB(id[tp[tv]], id[tv]), tv = f[tp[tv]];
	}
	int z = tu;
	if (tu != tv) {
		if (dep[tu] > dep[tv]) su.EB(id[tv] + 1, id[tu]), z = tv;
		else sv.EB(id[tu] + 1, id[tv]), z = tu;
	}
	pa = -2E9;
	ea = dep[u], eb = dep[v] - 2 * dep[z];
	int lst = 0;
	for (const auto& [l, r] : su) {
		int x = rnk[r];
		int mxd = mx[x].se == lst ? smx[x].fi : mx[x].fi;
		i64 na = mxd - dep[x], nb = mxd + dep[x];
		upd(na, nb);
		if (l < r) query(1, 1, n, l, r - 1);
		lst = rnk[l];
	}
	i64 al = pa + ea; int la = lst;
	pa = -2E9;
	ea = dep[v], eb = dep[u] - 2 * dep[z];
	lst = 0;
	swap(A, B);
	for (const auto& [l, r] : sv) {
		int x = rnk[r];
		int mxd = mx[x].se == lst ? smx[x].fi : mx[x].fi;
		i64 na = mxd - dep[x], nb = mxd + dep[x];
		upd(na, nb);
		if (l < r) query(1, 1, n, l, r - 1);
		lst = rnk[l];
	}
	i64 bl = pa + ea; int lb = lst;
	swap(A, B);
	ans = max(ans, al * A + bl * B);
	int mxd = mx[z].se == la || mx[z].se == lb ? (smx[z].se == la || smx[z].se == lb ? tmx[z].fi : smx[z].fi) : mx[z].fi;
	if (u != z) ans = max(ans, al * A + max(dep[z] + mxd, mxl[z] + dep[v] - dep[z]) * B);
	if (v != z) ans = max(ans, max(dep[z] + mxd, mxl[z] + dep[u] - dep[z]) * A + bl * B);
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i < n; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u].PB({v, w}), g[v].PB({u, w});
	}
	dfs(1, 0), dfs2(1, 0, 1), dfs3(1, 0);
	build(1, 1, n);
	for (int i = 1; i <= q; i++) {
		int u, v;
		scanf("%d%d%d%d", &u, &v, &A, &B);
		ans = 0, solve(u, v);
		printf("%lld\n", ans);
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 32348kb

input:

6 4
1 2 4
2 5 5
2 3 7
3 6 5
3 4 4
1 4 1 1
1 4 2 1
5 6 1 1
5 6 1 10

output:

18
32
18
160

result:

ok 4 number(s): "18 32 18 160"

Test #2:

score: 0
Accepted
time: 0ms
memory: 34572kb

input:

2 1
1 2 1
1 2 1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 32540kb

input:

2 10
1 2 2
1 2 1 1
1 2 1 2
1 2 1 3
1 2 2 1
1 2 2 2
1 2 3 1
1 2 3 2
1 2 3 3
1 2 2 3
1 2 1 3

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #4:

score: -100
Wrong Answer
time: 151ms
memory: 36604kb

input:

10 500000
4 5 576
5 8 218
1 10 678
1 9 2540
7 8 2023
2 7 5510
2 9 8454
4 6 22
3 9 5248
2 5 35782 82142
1 2 95412 85188
4 5 82466 22193
3 6 22169 67901
4 10 67229 30987
1 10 68282 17858
1 8 53726 3246
5 8 13913 74110
2 8 30052 7204
1 4 95255 48216
2 5 41392 98997
3 8 8435 5947
1 5 22067 21610
7 9 343...

output:

674365186
1454303268
477920681
1359445921
1501996827
1320778726
889342640
1582045824
426346196
1792561801
789005461
166905972
478560756
75994082
343648830
901237204
420263788
1710700661
367767940
335240094
1852278021
1679904905
1055408048
1644275016
563316675
602184744
873340490
815015664
1356022267...

result:

wrong answer 14th numbers differ - expected: '71705653', found: '75994082'