QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#107989	#5458. Shortest Path Query	xcyle	AC ✓	1297ms	340840kb	C++14	1.9kb	2023-05-23 13:09:20	2023-05-23 13:09:22

Judging History

你现在查看的是测评时间为 2023-05-23 13:09:22 的历史记录

[2024-06-21 12:37:55]
管理员手动重测本题所有提交记录

测评结果：AC
用时：1126ms
内存：341172kb

查看

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-23 13:09:22]
评测

测评结果：100
用时：1297ms
内存：340840kb

查看

[2023-05-23 13:09:20]
提交

answer

/*

_/      _/       _/_/_/      _/      _/    _/           _/_/_/_/_/
 _/    _/      _/      _/     _/    _/     _/           _/
  _/  _/      _/               _/  _/      _/           _/
   _/_/       _/                 _/        _/           _/_/_/_/
  _/  _/      _/                 _/        _/           _/
 _/    _/      _/      _/        _/        _/           _/
_/      _/       _/_/_/          _/        _/_/_/_/_/   _/_/_/_/_/

*/
#include <bits/stdc++.h>
#define ll long long
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ru(i, l, r) for (int i = (l); i <= (r); i++)
#define rd(i, r, l) for (int i = (r); i >= (l); i--)
#define mid ((l + r) >> 1)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define sz(s) (int)s.size()
#define maxn 50005
using namespace std;
int read() {
	int x = 0, w = 0; char ch = getchar();
	while(!isdigit(ch)) w |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return w ? -x : x;
}
int n, m;
vector<pii> G[maxn], pt[maxn];
int chk(pii a, pii b, pii c) {
	return (ll)(b.fi - a.fi) * (b.se - c.se) >= (ll)(a.se - b.se) * (c.fi - b.fi);
}
int main() {
	n = read(), m = read();
	ru(i, 1, m) {
		int x = read(), y = read(), c = read();
		G[x].push_back(mp(y, c));
	}
	pt[1].push_back(mp(0, 0));
	ru(i, 1, n) {
		vector<pii> tmp = pt[i]; pt[i].clear();
		sort(tmp.begin(), tmp.end());
		for (auto x: tmp) {
			while(pt[i].size() > 2 && chk(pt[i][pt[i].size() - 2], pt[i].back(), x)) pt[i].pop_back();
			pt[i].push_back(x); 
		}
		for (auto V: G[i]) for (auto x: pt[i]) {
			pt[V.fi].push_back(mp(x.fi + 1 - V.se, x.se + V.se));
		}
	}
	int q = read();
	while(q--) {
		int a = read(), b = read(), i = read(); ll ans = 1e18;
		for (auto x: pt[i]) ans = min(ans, (ll)a * x.fi + (ll)b * x.se);
		printf("%lld\n", ans);
	}
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 3ms

memory: 5896kb

input:

output:

3
4
4

result:

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

Test #2:

score: 0

Accepted

time: 82ms

memory: 22128kb

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:

result:

ok 50000 numbers

Test #3:

score: 0

Accepted

time: 135ms

memory: 50700kb

input:

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

output:

100196045
31414400
96903432
4429901
131353947
100466556
96621590
116427456
86564241
138309577
111227766
96757449
98894394
113624940
103437724
32090169
118889544
27383865
145395709
52415186
44958306
178247166
101837390
123750212
66411806
29005113
61920301
53700468
83473964
101048973
24035890
82224385...

result:

ok 50000 numbers

Test #4:

score: 0

Accepted

time: 188ms

memory: 63052kb

input:

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

output:

result:

ok 50000 numbers

Test #5:

score: 0

Accepted

time: 489ms

memory: 167732kb

input:

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

output:

21363040
19817072
33235630
2642743
12734703
31561956
16868881
12347713
34007395
31539206
21812869
11469295
13583164
35332256
19432281
13050400
27543307
30865175
23535331
10932941
10731700
8935711
32438529
30147704
11201224
15475486
18918233
29097672
1865520
1717197
10847438
17918300
9085519
22377502...

result:

ok 50000 numbers

Test #6:

score: 0

Accepted

time: 692ms

memory: 209884kb

input:

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

output:

result:

ok 50000 numbers

Test #7:

score: 0

Accepted

time: 1050ms

memory: 307112kb

input:

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

output:

result:

ok 50000 numbers

Test #8:

score: 0

Accepted

time: 1237ms

memory: 340840kb

input:

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

output:

result:

ok 50000 numbers

Test #9:

score: 0

Accepted

time: 1297ms

memory: 338912kb

input:

50000 100000
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 0
7 8 0
8 9 0
9 10 0
10 11 1
11 12 0
12 13 1
13 14 0
14 15 0
15 16 1
16 17 1
17 18 0
18 19 1
19 20 1
20 21 0
21 22 1
22 23 1
23 24 0
24 25 0
25 26 0
26 27 0
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 0
36 37 0
37 38 0
38 39 1
...

output:

result:

ok 50000 numbers

Test #10:

score: 0

Accepted

time: 1215ms

memory: 339852kb

input:

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

output:

result:

ok 50000 numbers

Test #11:

score: 0

Accepted

time: 23ms

memory: 11432kb

input:

50000 99998
1 2 0
1 2 1
2 3 0
2 3 1
3 4 0
3 4 1
4 5 0
4 5 1
5 6 0
5 6 1
6 7 0
6 7 1
7 8 0
7 8 1
8 9 0
8 9 1
9 10 0
9 10 1
10 11 0
10 11 1
11 12 0
11 12 1
12 13 0
12 13 1
13 14 0
13 14 1
14 15 0
14 15 1
15 16 0
15 16 1
16 17 0
16 17 1
17 18 0
17 18 1
18 19 0
18 19 1
19 20 0
19 20 1
20 21 0
20 21 1
21...

output:

result:

ok 50000 numbers

Test #12:

score: 0

Accepted

time: 247ms

memory: 133488kb

input:

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

output:

result:

ok 50000 numbers