QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#294860#5458. Shortest Path Queryushg8877TL 928ms32436kbC++141.4kb2023-12-30 17:02:092024-06-21 12:39:01

Judging History

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

  • [2024-06-21 12:39:01]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:928ms
  • 内存:32436kb
  • [2023-12-30 17:02:09]
  • 评测
  • 测评结果:100
  • 用时:1822ms
  • 内存:91068kb
  • [2023-12-30 17:02:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=5e4+5;
int n,m,q;
struct Point{
	int x,y;
	Point(int _x=0,int _y=0){x=_x,y=_y;} 
};
Point operator -(Point x,Point y){return (Point){x.x-y.x,x.y-y.y};} 
ll operator *(Point x,Point y){return x.x*y.y-x.y*y.x;} 
vector<Point> conh[MAXN];
vector<pair<int,int> > edg[MAXN];
vector<Point> solve(vector<Point> p){
	static Point st[MAXN]; static int top;
	top=0;
	sort(p.begin(),p.end(),[&](Point x,Point y){return atan2(x.x,x.y)>atan2(y.x,y.y);});
	for(Point q:p)if(!top||q.x<st[top].x||q.y<st[top].y){
		while(top>=2&&(q-st[top])*(q-st[top-1])<=0||top&&st[top].x>=q.x&&st[top].y>=q.y) top--;
		st[++top]=q;
	}
	p.clear();
	for(int i=1;i<=top;i++) p.push_back(st[i]);
	return p;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	conh[1].push_back(Point(0,0));
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		edg[v].push_back(MP(u,w));
	}
	for(int i=2;i<=n;i++){
		vector<Point> nds;
		for(auto e:edg[i]) for(auto p:conh[e.first])
			nds.push_back(Point(p.x+(e.second==1),p.y+(e.second==0)));
		conh[i]=solve(nds);
	}
	cin>>q;
	while(q--){
		int a,b,x;cin>>b>>a>>x;
		int ans=1e9;
		auto cal=[&](int id){
			auto p=conh[x][id];
			int r=a*p.x+b*p.y;
			ans=min(ans,r);
			return r; 
		};
		for(int i=0;i<conh[x].size();i++) cal(i);
		cout<<ans<<endl;
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 6676kb

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: 0
Accepted
time: 217ms
memory: 15972kb

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:

164602050
208733870
228180204
248456409
87574800
16685198
46684062
64713954
46949896
240633535
94777502
83016099
259833741
167838804
214963500
147454419
111021650
80187604
184782450
78138570
86528820
203553394
188095596
202049239
290053220
172790198
168899028
97757186
96431009
266952297
164349486
26...

result:

ok 50000 numbers

Test #3:

score: 0
Accepted
time: 672ms
memory: 26596kb

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: 928ms
memory: 32436kb

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:

41086586
22479083
65941117
52313422
27188549
98552837
41170647
18070874
39704907
37300025
33494097
12541197
85953980
97466762
54255520
55975530
82137682
80760412
36734523
80227468
57771407
53423371
35392992
38772417
24348238
129485865
50694526
41529532
35522018
64188507
64483980
20809109
88158268
62...

result:

ok 50000 numbers

Test #5:

score: -100
Time Limit Exceeded

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: