QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75434#5458. Shortest Path QueryzhouhuanyiWA 53ms17632kbC++112.1kb2023-02-05 10:30:492024-06-21 12:37:00

Judging History

你现在查看的是最新测评结果

  • [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;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 8404kb

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: 53ms
memory: 17632kb

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'