QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168816#5458. Shortest Path QuerysyksykCCCWA 57ms9128kbC++142.0kb2023-09-08 22:40:452023-09-08 22:40:45

Judging History

你现在查看的是测评时间为 2023-09-08 22:40:45 的历史记录

  • [2024-06-21 12:38:17]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:69ms
  • 内存:9328kb
  • [2023-09-08 22:40:45]
  • 评测
  • 测评结果:0
  • 用时:57ms
  • 内存:9128kb
  • [2023-09-08 22:40:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<pair<int, int>> vpii;
const int N = 5e4 + 5, M = 1e5 + 5, R = 1023;
vpii G[N], conv[R + 1]; // (w = 0, w = 1)
struct query { ll u, a, b, id, ans; } Q[N]; 
int n, m, q;
void add(vpii &c, int x, int y) {
	if(c.empty()) { c.emplace_back(x, y); return; }
	if(c.back().second <= y) return;
	if(c.back().first == x)	y = min(c.back().second, y), c.pop_back();
	while(c.size() > 1) {
		int e = (int)c.size() - 1;
		if((ll)(c[e-1].second - c[e].second) * (c[e].first - x) 
			<= (ll)(c[e].second - y) * (c[e-1].first - c[e].first)) c.pop_back();
		else break;
	}
	c.emplace_back(x, y);
}
vpii merge(const vpii &A, const vpii &B, int dx, int dy) {
	int i = 0, j = 0;
	vpii res;
	while(i < A.size() && j < B.size()) {
		if(A[i].first <= B[j].first + dx) add(res, A[i].first, A[i].second), i++;
		else add(res, B[j].first + dx, B[j].second + dy), j++;
	}
	for(; i < A.size(); i++) add(res, A[i].first, A[i].second);
	for(; j < B.size(); j++) add(res, B[j].first + dx, B[j].second + dy);
	return res;
}
int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		G[v].emplace_back(u, c); // reversed edge
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; i++) {
		scanf("%lld %lld %lld", &Q[i].a, &Q[i].b, &Q[i].u);
		Q[i].id = i;
	}
	sort(Q + 1, Q + q + 1, [&](const query &A, const query &B){ return A.u < B.u; });
	conv[1].emplace_back(0, 0);
	int cur = 1;
	for(int u = 1; u <= n; u++) {
		if(u > R) conv[u & R].clear();
		for(auto e : G[u]) {
			int v = e.first, w = e.second;
			conv[u & R] = merge(conv[u & R], conv[v & R], w == 0, w == 1);
		}
		while(cur <= q && Q[cur].u == u) {
			ll ans = LLONG_MAX;
			for(auto p : conv[u & R]) {
				ans = min(ans, p.first * Q[cur].a + p.second * Q[cur].b);
			}
			Q[cur++].ans = ans;
		}
	}
	sort(Q + 1, Q + q + 1, [&](const query &A, const query &B){ return A.id < B.id; });
	for(int i = 1; i <= q; i++) printf("%lld\n", Q[i].ans);
	return 0;
}

詳細信息

Test #1:

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

input:

4 4
1 2 0
1 3 1
2 4 0
3 4 1
3
3 5 2
3 2 4
2 3 4

output:

3
4
4

result:

ok 3 number(s): "3 4 4"

Test #2:

score: -100
Wrong Answer
time: 57ms
memory: 9128kb

input:

50000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 9 1
9 10 0
10 11 1
11 12 1
12 13 1
13 14 0
14 15 0
15 16 0
16 17 0
17 18 1
18 19 1
19 20 0
20 21 1
21 22 0
22 23 0
23 24 1
24 25 1
25 26 0
26 27 1
27 28 0
28 29 0
29 30 0
30 31 0
31 32 1
32 33 0
33 34 1
34 35 1
35 36 1
36 37 1
37 38 0
38 39 0
...

output:

171090050
213493702
236693474
259699419
89732820
16685198
47102088
64713954
46949896
245672377
94777502
84753103
267419449
173654876
216482422
147454419
111021650
80187604
184782450
78138570
86528820
207116030
191332392
202049239
297586630
173714177
174899498
97998224
96431009
280559577
164349486
27...

result:

wrong answer 1st numbers differ - expected: '164602050', found: '171090050'