QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334161#6111. Two PathsFISHER_WA 165ms29216kbC++144.6kb2024-02-21 11:55:292024-02-21 11:55:29

Judging History

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

  • [2024-02-21 11:55:29]
  • 评测
  • 测评结果:WA
  • 用时:165ms
  • 内存:29216kb
  • [2024-02-21 11:55:29]
  • 提交

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].se : mx[x].se;
		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);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 28876kb

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: 27908kb

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: 29216kb

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: 165ms
memory: 28912kb

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
476601225
1359445921
1501996827
1320778726
889342640
1573781502
426346196
1792561801
789005461
166905972
478560756
75994082
334573104
901237204
420263788
1710700661
367767940
307415352
1840589883
1679904905
1054831274
1644275016
79164180
602184744
873340490
815015664
1356022267
...

result:

wrong answer 3rd numbers differ - expected: '477920681', found: '476601225'