QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75434#5458. Shortest Path QueryzhouhuanyiWA 71ms17468kbC++112.1kb2023-02-05 10:30:492023-02-05 10:30:53

Judging History

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

  • [2024-06-21 12:37:00]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:53ms
  • 内存:17632kb
  • [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:30:53]
  • 评测
  • 测评结果:0
  • 用时:71ms
  • 内存:17468kb
  • [2023-02-05 10:30:49]
  • 提交

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'