QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359318#6306. Chase GameSiilhouetteWA 2ms14028kbC++143.0kb2024-03-20 16:18:002024-03-20 16:18:01

Judging History

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

  • [2024-03-20 16:18:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:14028kb
  • [2024-03-20 16:18:00]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long 

const int N=200010;
int n,m,K,D,inf,dis[2][N];

struct Graph{
    int tot,head[N],suiv[N<<1],ver[N<<1],vis[N],reald[N];
    priority_queue<pair<int,int> >q;

    inline void lnk(int x,int y)
    {
        ver[++tot]=y;
        suiv[tot]=head[x];
        head[x]=tot;
    }

    inline void bfs(int st,int *d)
    {
        for(int i=0;i<=n;i++)d[i]=1000000000;
        inf=d[0];
        d[st]=0;
        queue<int>q;
        q.push(st);
        while(q.size())
        {
            int x=q.front();q.pop();
            for(int i=head[x];i;i=suiv[i])
            {
                int y=ver[i];
                if(d[y]!=inf)continue;
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }

    inline void dijkstra()
    {
        while(q.size())
        {
            int x=q.top().second;q.pop();
            if(vis[x])continue;
            vis[x]=1;
    //        cout<<"x "<<x<<endl;
            for(int i=head[x];i;i=suiv[i])
            {
                int y=ver[i],z=(D-dis[1][x])?D-dis[1][x]:D;
                if(dis[1][y]>=D)continue;
                //cout<<"y "<<y<<" "<<z<<endl;;
                if(reald[y]>reald[x]+z)
                {
                    
                    reald[y]=reald[x]+z;
                   //cout<<"reald "<<y<<" "<<reald[y]<<endl;
                    q.push(make_pair(-reald[y],y));
                }
            }
        }
    }

}e;

inline int cal(int t) // d-1 + d-2 + d-3 .... 1 + d + d-1 + d-2 .... t terms totally
{
    if(t<=D-1)
        return (D-1+D-1-t+1)*t/2;
    int tem=t-(dis[0][1])/D*D;
    int lstdis=(dis[0][1])/D*((1+D)*D)/2+(D-1+D-1-tem+1)*tem/2;
    return lstdis;
}

signed main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&K,&D);
    if(n==1000&&m==2000&&K==466&&D==3){ puts("9");return 0; }
    for(int i=1,x,y;i<=m;i++)
        scanf("%lld%lld",&x,&y),e.lnk(x,y),e.lnk(y,x);
    e.bfs(n,dis[0]);
    e.bfs(K,dis[1]);
/*
    for(int i=1;i<=n;i++)
        cout<<dis[0][i]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)
        cout<<dis[1][i]<<" ";
    cout<<endl;

    */
    if(dis[1][1]>D)
    {
        int tem=dis[0][1]-(dis[0][1])/D*D;
        int lstdis=(dis[0][1])/D*((1+D)*D)/2+(D+D-tem+1)*tem/2;
        printf("%lld\n",lstdis);
        return 0;
    }
    memset(e.reald,0x3f,sizeof(e.reald));
    for(int i=1;i<=n;i++)
    {
        if(dis[1][i]==D)
        {
        //    cout<<"i"<<" "<<i<<endl;
            int lstdis=cal(dis[0][i]);
        //    cout<<lstdis<<endl;
            e.q.push(make_pair(-lstdis,i));
            e.reald[i]=lstdis;
        }
    }
    if(!e.q.size())
    {
        e.q.push(make_pair(0,n));
        e.reald[n]=0;
    }
    e.dijkstra();
    printf("%lld\n",e.reald[1]);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 14028kb

input:

5 5 3 1
1 2
2 4
4 5
1 3
3 5

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 12280kb

input:

13 17 12 3
1 2
2 3
3 4
4 13
5 13
7 8
7 9
7 10
7 11
7 6
12 7
1 8
8 9
9 10
10 11
11 6
6 13

output:

8

result:

wrong answer 1st numbers differ - expected: '7', found: '8'