QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#294852 | #5458. Shortest Path Query | ushg8877 | WA | 108ms | 14268kb | C++14 | 1.4kb | 2023-12-30 16:59:05 | 2023-12-30 16:59:06 |
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){
while(top>=2&&(q-st[top])*(q-st[top-1])>=0) 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: 2ms
memory: 6380kb
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: 108ms
memory: 14268kb
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:
194826300 240573628 268778434 296599514 101215280 17433588 52651028 65842124 47441376 277065662 96151412 95582418 302923294 196921966 242206932 155982714 116885900 84052424 202775300 79665902 90237270 232679612 215325552 224093234 335907280 194160862 198769788 109346944 101775854 321335662 178859316...
result:
wrong answer 1st numbers differ - expected: '164602050', found: '194826300'