QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#75434 | #5458. Shortest Path Query | zhouhuanyi | WA | 71ms | 17468kb | C++11 | 2.1kb | 2023-02-05 10:30:49 | 2023-02-05 10:30:53 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<cassert>
#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;
bool operator < (const points &t)const
{
return x!=t.x?x<t.x:y<t.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]<B[ps2])) 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);
}
for (int j=1;j<dp[i].size();++j) assert(dp[i][j-1]<dp[i][j]);
}
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: 1ms
memory: 8248kb
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: 71ms
memory: 17468kb
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:
wrong answer 25002nd numbers differ - expected: '33097025', found: '34974005'