QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75428#5458. Shortest Path QueryzhouhuanyiWA 96ms17612kbC++111.9kb2023-02-05 10:21:122023-02-05 10:21:14

Judging History

你现在查看的是测评时间为 2023-02-05 10:21:14 的历史记录

  • [2024-06-21 12:36:58]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:48ms
  • 内存:17852kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 10:21:14]
  • 评测
  • 测评结果:0
  • 用时:96ms
  • 内存:17612kb
  • [2023-02-05 10:21:12]
  • 提交

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'