QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#294841 | #5458. Shortest Path Query | ushg8877 | WA | 0ms | 6444kb | C++14 | 1.4kb | 2023-12-30 16:55:51 | 2023-12-30 16:55:52 |
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);
for(auto p:conh[i]) cout<<p.x<<' '<<p.y<<endl;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 6444kb
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:
0 1 1 0 2 0 0 2 3 4 4
result:
wrong answer 1st numbers differ - expected: '3', found: '0'