QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#745932#6306. Chase Gamedezex#WA 1ms6652kbC++202.2kb2024-11-14 12:29:062024-11-14 12:29:06

Judging History

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

  • [2024-11-14 12:29:06]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6652kb
  • [2024-11-14 12:29:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
vector<int> nb[N];
ll ds[N],dk[N],dt[N];
int vis[N];
int n,m,k;ll rg;
bool flag[N];

void bfs(int s, ll *dis)
{
    //dis all -1
    queue<int> q;
    q.push(s);dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(auto v:nb[u])
        {
            if(dis[v] != -1)
                continue;
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
}


void dij(int s,ll *d)
{
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[s]=0;
    priority_queue<pair<ll,int>> q;
    q.push(make_pair(0,1));
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        // if(u==n)
        //     break;
        if(rg - dk[u] <= 0 && u!=s)
        {
            flag[u]=true;
            continue;
        };
        for(auto v:nb[u])
        {
            if(vis[v])
                continue;
            d[v]=d[u]+max(0ll,rg-dk[v]);
            // printf("%d->%d\n",u,v);
            vis[v]=1;
            q.push(make_pair(-d[v],v));
        };
    }
}

inline ll calc(ll l)
{
    ll ans = (l/rg) * ((rg+1)*rg/2);
    ll k = l%rg;
    ans += (rg+rg+k-1) * k / 2;
    return ans;
}

int main()
{
    scanf("%d %d %d %lld",&n,&m,&k,&rg);
    for(int i=1;i<=m;i++)
    {
        int u,v;scanf("%d %d",&u,&v);
        nb[u].push_back(v);
        nb[v].push_back(u);
    };
    memset(dk,-1,sizeof(dk));
    memset(dt,-1,sizeof(dt));
    bfs(k, dk);
    bfs(n, dt);
    dij(1, ds);
    // for(int i=1;i<=n;i++)
    //     printf("dk[%d]=%lld\n",i,dk[i]);
    // printf("\n");
    // for(int i=1;i<=n;i++)
    //     printf("dt[%d]=%lld\n",i,dt[i]);
    // printf("\n");
    // for(int i=1;i<=n;i++)
    //     printf("ds[%d]=%lld\n",i,ds[i]);
    // printf("\n");

    // printf("flag:\n");
    ll ans=-1;
    for(int u=1;u<=n;u++)
        if(flag[u])
        {
            // printf("%d ",u);
            ll t = ds[u] + calc(dt[u]+1);
            ans = ans==-1?t:min(t,ans);
        };
    // printf("\n");
    printf("%lld\n",ans);
    return 0;
}


詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5884kb

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: 0
Accepted
time: 1ms
memory: 5704kb

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:

7

result:

ok 1 number(s): "7"

Test #3:

score: 0
Accepted
time: 1ms
memory: 6068kb

input:

10 9 4 1
4 3
1 2
7 6
6 5
8 9
9 10
5 4
8 7
3 2

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5744kb

input:

10 20 9 1
9 5
2 9
4 5
10 5
7 3
1 8
7 1
7 5
3 4
3 1
7 8
3 8
9 3
10 6
9 1
1 6
8 5
6 2
1 10
2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 6652kb

input:

10 20 3 1
1 4
6 7
5 4
5 3
2 1
8 1
7 8
2 6
2 4
4 8
9 5
1 10
7 4
5 8
4 10
2 5
6 10
4 6
3 7
1 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 1ms
memory: 5952kb

input:

10 20 4 1
2 7
6 4
2 3
2 4
6 5
8 5
6 7
10 2
3 10
1 8
3 9
3 7
1 7
5 1
6 1
3 4
2 1
5 2
9 2
9 10

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 5988kb

input:

10 20 1 10
10 9
2 5
7 8
7 10
10 8
8 9
5 6
3 1
6 4
7 9
2 3
3 6
2 1
8 6
5 8
7 4
4 3
2 4
4 1
9 6

output:

-1

result:

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