QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#75428 | #5458. Shortest Path Query | zhouhuanyi | WA | 96ms | 17612kb | C++11 | 1.9kb | 2023-02-05 10:21:12 | 2023-02-05 10:21:14 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#define N 100000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int num,data;
};
struct points
{
int x,y;
};
points operator - (points a,points b)
{
return (points){a.x-b.x,a.y-b.y};
}
long long operator * (points a,points b)
{
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
int n,m,q,lg[N+1];
vector<reads>E[N+1];
vector<points>dp[N+1];
bool check(points a,points b,points c)
{
return (c-a)*(b-a)>=0;
}
vector<points>merge(vector<points>A,vector<points>B)
{
vector<points>C;
vector<points>D;
int ps=0,ps2=0;
while (ps<A.size()||ps2<B.size())
{
if (ps<A.size()&&(ps2==B.size()||A[ps].x<B[ps2].x)) C.push_back(A[ps]),ps++;
else C.push_back(B[ps2]),ps2++;
}
for (int i=0;i<C.size();++i)
{
if (D.size()>=2&&check(D[(int)(D.size())-2],D.back(),C[i])) D.pop_back();
D.push_back(C[i]);
}
return D;
}
int main()
{
int a,b,x,y,z,d;
vector<points>p;
n=read(),m=read();
for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),E[y].push_back((reads){x,z});
dp[1].push_back((points){0,0});
for (int i=2;i<=n;++i)
for (int j=0;j<E[i].size();++j)
{
p=dp[E[i][j].num];
if (!E[i][j].data)
{
for (int k=0;k<p.size();++k) p[k].x++;
}
else
{
for (int k=0;k<p.size();++k) p[k].y++;
}
dp[i]=merge(dp[i],p);
}
q=read();
while (q--)
{
a=read(),b=read(),x=read(),d=0;
for (int i=lg[dp[x].size()];i>=0;--i)
if (d+(1<<i)<dp[x].size()&&1ll*a*dp[x][d+(1<<i)].x+1ll*b*dp[x][d+(1<<i)].y<1ll*a*dp[x][d+(1<<i)-1].x+1ll*b*dp[x][d+(1<<i)-1].y)
d+=(1<<i);
printf("%lld\n",1ll*a*dp[x][d].x+1ll*b*dp[x][d].y);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8268kb
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: 96ms
memory: 17612kb
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:
164607690 208733870 228180204 248461791 87574800 16687154 46684062 64724018 46957654 240641790 94792630 83018946 259844014 167838804 214968900 147469032 111033430 80196630 184782450 78138570 86528820 203553394 188101584 202054800 290053220 172794342 168906234 97759344 96440890 266954781 164358786 26...
result:
wrong answer 1st numbers differ - expected: '164602050', found: '164607690'