oj.uz

Submission #750508

# Submission time Handle Problem Language Result Execution time Memory
750508 2023-05-29T15:12:33 Z arnold518 Cyberland (APIO23_cyberland) C++17
97 / 100
 974 ms 64212 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)
        {
            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 23 ms 2772 KB Correct.
2 Correct 19 ms 2772 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3328 KB Correct.
2 Correct 26 ms 3292 KB Correct.
3 Correct 26 ms 3360 KB Correct.
4 Correct 26 ms 3304 KB Correct.
5 Correct 29 ms 3284 KB Correct.
6 Correct 31 ms 8724 KB Correct.
7 Correct 32 ms 8696 KB Correct.
8 Correct 21 ms 14880 KB Correct.
9 Correct 26 ms 2788 KB Correct.
10 Correct 24 ms 2780 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3284 KB Correct.
2 Correct 22 ms 3292 KB Correct.
3 Correct 24 ms 3284 KB Correct.
4 Correct 26 ms 2772 KB Correct.
5 Correct 26 ms 2788 KB Correct.
6 Correct 7 ms 7624 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 38520 KB Correct.
2 Correct 74 ms 3304 KB Correct.
3 Correct 67 ms 3360 KB Correct.
4 Correct 67 ms 3292 KB Correct.
5 Correct 76 ms 2772 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3412 KB Correct.
2 Correct 31 ms 3404 KB Correct.
3 Correct 27 ms 3404 KB Correct.
4 Correct 28 ms 8844 KB Correct.
5 Correct 26 ms 2784 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3412 KB Correct.
2 Correct 24 ms 3412 KB Correct.
3 Correct 82 ms 49592 KB Correct.
4 Correct 26 ms 7124 KB Correct.
5 Correct 24 ms 2772 KB Correct.
6 Correct 23 ms 3412 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 3484 KB Correct.
2 Correct 21 ms 3732 KB Correct.
3 Correct 562 ms 61684 KB Correct.
4 Correct 245 ms 16212 KB Correct.
5 Correct 418 ms 27296 KB Correct.
6 Correct 179 ms 12872 KB Correct.
7 Correct 290 ms 17480 KB Correct.
8 Correct 151 ms 5044 KB Correct.
9 Correct 78 ms 3488 KB Correct.
10 Correct 75 ms 3512 KB Correct.
11 Correct 117 ms 3644 KB Correct.
12 Correct 88 ms 3400 KB Correct.
13 Correct 79 ms 3456 KB Correct.
14 Correct 268 ms 31544 KB Correct.
15 Correct 212 ms 10388 KB Correct.
16 Correct 90 ms 3448 KB Correct.
17 Correct 86 ms 3388 KB Correct.
18 Correct 78 ms 3452 KB Correct.
19 Correct 144 ms 3360 KB Correct.
20 Correct 8 ms 2772 KB Correct.
21 Correct 9 ms 3232 KB Correct.
22 Correct 15 ms 3756 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 3424 KB Correct.
2 Correct 38 ms 3824 KB Correct.
3 Incorrect 974 ms 64212 KB Wrong Answer.
4 Halted 0 ms 0 KB -