QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168373#5458. Shortest Path QuerysyksykCCCWA 47ms9068kbC++142.1kb2023-09-08 12:46:452023-09-08 12:46:46

Judging History

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

  • [2024-06-21 12:38:14]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:38ms
  • 内存:9132kb
  • [2023-09-08 12:46:46]
  • 评测
  • 测评结果:0
  • 用时:47ms
  • 内存:9068kb
  • [2023-09-08 12:46: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 = 1001;
vpii G[N], conv[R]; // (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[i].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;
		}
	}
	assert(cur == q + 1);
	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: 1ms
memory: 4896kb

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: 47ms
memory: 9068kb

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:

185638090
213784513
237038034
273658506
89856130
17284446
47161678
65617298
47343432
270809489
95877614
93424311
295847953
173904741
237080454
154283163
115717250
83282228
184975675
78154972
86568645
207390557
210544104
219700223
297998155
190086169
193452259
107085328
100710713
287129781
175967742
...

result:

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