oj.uz

Submission #750554

# Submission time Handle Problem Language Result Execution time Memory
750554 2023-05-29T17:21:21 Z arnold518 Cyberland (APIO23_cyberland) C++17
97 / 100
 930 ms 64216 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];

bool vis[MAXN+10];
double dist[MAXN+10][70], P[70];

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, 60);

    for(int i=1; i<=N; i++) vis[i]=false;

    queue<int> Q;
    vis[1]=true; Q.push(1); vis[H]=true;
    while(!Q.empty())
    {
        int now=Q.front(); Q.pop();
        for(auto nxt : adj[now])
        {
            if(vis[nxt.first]) continue;
            Q.push(nxt.first);
            vis[nxt.first]=true;
        }
    }
    for(int i=1; i<=N; i++) if(A[i]==0 && !vis[i]) A[i]=1;

    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;
    A[1]=0;

    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(nxt.first!=H && 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 && now.k!=K)
        {
            for(auto nxt : adj[now.v])
            {
                if(nxt.first!=H && 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>INF-100) ans=-1;
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2772 KB Correct.
2 Correct 21 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3356 KB Correct.
2 Correct 27 ms 3332 KB Correct.
3 Correct 26 ms 3340 KB Correct.
4 Correct 27 ms 3348 KB Correct.
5 Correct 30 ms 3352 KB Correct.
6 Correct 25 ms 8772 KB Correct.
7 Correct 31 ms 8660 KB Correct.
8 Correct 19 ms 14876 KB Correct.
9 Correct 25 ms 2772 KB Correct.
10 Correct 27 ms 2784 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3436 KB Correct.
2 Correct 25 ms 3292 KB Correct.
3 Correct 21 ms 3288 KB Correct.
4 Correct 25 ms 2784 KB Correct.
5 Correct 23 ms 2784 KB Correct.
6 Correct 9 ms 7588 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 38524 KB Correct.
2 Correct 70 ms 3332 KB Correct.
3 Correct 65 ms 3332 KB Correct.
4 Correct 69 ms 3328 KB Correct.
5 Correct 77 ms 2776 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3428 KB Correct.
2 Correct 28 ms 3412 KB Correct.
3 Correct 26 ms 3408 KB Correct.
4 Correct 28 ms 8864 KB Correct.
5 Correct 25 ms 2784 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3388 KB Correct.
2 Correct 21 ms 3424 KB Correct.
3 Correct 62 ms 49612 KB Correct.
4 Correct 18 ms 7124 KB Correct.
5 Correct 24 ms 2792 KB Correct.
6 Correct 24 ms 3416 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3416 KB Correct.
2 Correct 25 ms 3796 KB Correct.
3 Correct 590 ms 61760 KB Correct.
4 Correct 225 ms 16296 KB Correct.
5 Correct 369 ms 27308 KB Correct.
6 Correct 194 ms 12872 KB Correct.
7 Correct 241 ms 17476 KB Correct.
8 Correct 148 ms 4980 KB Correct.
9 Correct 85 ms 3532 KB Correct.
10 Correct 71 ms 3408 KB Correct.
11 Correct 116 ms 3588 KB Correct.
12 Correct 92 ms 3484 KB Correct.
13 Correct 92 ms 3456 KB Correct.
14 Correct 253 ms 31532 KB Correct.
15 Correct 220 ms 10480 KB Correct.
16 Correct 85 ms 3404 KB Correct.
17 Correct 87 ms 3560 KB Correct.
18 Correct 78 ms 3460 KB Correct.
19 Correct 153 ms 3404 KB Correct.
20 Correct 8 ms 2776 KB Correct.
21 Correct 9 ms 3284 KB Correct.
22 Correct 14 ms 3796 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 3484 KB Correct.
2 Correct 40 ms 3776 KB Correct.
3 Incorrect 930 ms 64216 KB Wrong Answer.
4 Halted 0 ms 0 KB -