oj.uz

Submission #750493

# Submission time Handle Problem Language Result Execution time Memory
750493 2023-05-29T14:54:29 Z arnold518 Cyberland (APIO23_cyberland) C++17
8 / 100
 74 ms 24652 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const double INF = 1e18;
const double eps = 1e-10;

int N, M, K, H, A[MAXN+10];
vector<pii> adj[MAXN+10];

double dist[MAXN+10][40], P[40];

struct Queue
{
    int v, k; double w;
    bool operator < (const Queue &p) const { return w>p.w; }
};

double solve(int _N, int _M, int _K, int _H, std::vector<int> _x, std::vector<int> _y, std::vector<int> _c, std::vector<int> _arr) {
    N=_N; M=_M; K=_K; H=_H+1;
    for(int i=1; i<=N; i++) A[i]=_arr[i-1];
    for(int i=0; i<M; i++)
    {
        int u=_x[i]+1, v=_y[i]+1, w=_c[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    K=min(K, 30);

    for(int i=1; i<=N; i++) for(int j=0; j<=K; j++) dist[i][j]=INF;
    priority_queue<Queue> PQ;
    dist[H][0]=0;
    PQ.push({H, 0, 0});

    P[0]=1;
    for(int i=1; i<=K; i++) P[i]=P[i-1]/2;

    while(!PQ.empty())
    {
        Queue now=PQ.top(); PQ.pop();
        if(fabs(dist[now.v][now.k]-now.w)>eps) continue;

        //printf("%d %d %.10lf\n", now.v, now.k, now.w);
        if(A[now.v]==0) continue;
        for(auto nxt : adj[now.v])
        {
            if(now.w+P[now.k]*nxt.second<dist[nxt.first][now.k])
            {
                dist[nxt.first][now.k]=now.w+P[now.k]*nxt.second;
                PQ.push({nxt.first, now.k, now.w+P[now.k]*nxt.second});
            }
        }
        if(A[now.v]==2)
        {
            for(auto nxt : adj[now.v])
            {
                if(now.w+P[now.k+1]*nxt.second<dist[nxt.first][now.k+1])
                {
                    dist[nxt.first][now.k+1]=now.w+P[now.k+1]*nxt.second;
                    PQ.push({nxt.first, now.k+1, now.w+P[now.k+1]*nxt.second});
                }

            }
        }
    }
    double ans=INF;
    for(int i=1; i<=N; i++)
    {
        adj[i].clear();
        for(int j=0; j<=K; j++)
        {
            if(A[i]==0 || i==1) ans=min(ans, dist[i][j]);
            dist[i][j]=0;
        }
    }
    if(ans==-1) ans=0;
    return ans;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 2900 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3028 KB Correct.
2 Correct 28 ms 3100 KB Correct.
3 Correct 26 ms 3068 KB Correct.
4 Correct 26 ms 3028 KB Correct.
5 Correct 27 ms 3080 KB Correct.
6 Correct 26 ms 6440 KB Correct.
7 Correct 32 ms 6356 KB Correct.
8 Correct 17 ms 10196 KB Correct.
9 Correct 24 ms 2748 KB Correct.
10 Correct 24 ms 2752 KB Correct.

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3028 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 24652 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 3148 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3156 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 3208 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 3232 KB Wrong Answer.
2 Halted 0 ms 0 KB -