QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#75428 | #5458. Shortest Path Query | zhouhuanyi | WA | 48ms | 17852kb | C++11 | 1.9kb | 2023-02-05 10:21:12 | 2024-06-21 12:36:58 |
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8424kb
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: 48ms
memory: 17852kb
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'