QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#294860 | #5458. Shortest Path Query | ushg8877 | TL | 928ms | 32436kb | C++14 | 1.4kb | 2023-12-30 17:02:09 | 2024-06-21 12:39:01 |
Judging History
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...