oj.uz

Submission #750507

# Submission time Handle Problem Language Result Execution time Memory
750507 2023-05-29T15:11:25 Z arnold518 Cyberland (APIO23_cyberland) C++17
97 / 100
 566 ms 40716 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][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++) 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 19 ms 2772 KB Correct.
2 Correct 22 ms 2768 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3108 KB Correct.
2 Correct 25 ms 3124 KB Correct.
3 Correct 26 ms 3096 KB Correct.
4 Correct 25 ms 3112 KB Correct.
5 Correct 26 ms 3104 KB Correct.
6 Correct 22 ms 6484 KB Correct.
7 Correct 30 ms 6364 KB Correct.
8 Correct 18 ms 10196 KB Correct.
9 Correct 24 ms 2776 KB Correct.
10 Correct 26 ms 2756 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3044 KB Correct.
2 Correct 22 ms 3100 KB Correct.
3 Correct 23 ms 3156 KB Correct.
4 Correct 26 ms 2756 KB Correct.
5 Correct 28 ms 2768 KB Correct.
6 Correct 7 ms 5716 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 24824 KB Correct.
2 Correct 69 ms 3088 KB Correct.
3 Correct 67 ms 3028 KB Correct.
4 Correct 74 ms 3020 KB Correct.
5 Correct 74 ms 2748 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3164 KB Correct.
2 Correct 25 ms 3156 KB Correct.
3 Correct 26 ms 3140 KB Correct.
4 Correct 33 ms 6528 KB Correct.
5 Correct 22 ms 2644 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3112 KB Correct.
2 Correct 20 ms 3084 KB Correct.
3 Correct 54 ms 31888 KB Correct.
4 Correct 17 ms 5460 KB Correct.
5 Correct 24 ms 2768 KB Correct.
6 Correct 24 ms 3156 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 3244 KB Correct.
2 Correct 23 ms 3328 KB Correct.
3 Correct 566 ms 39456 KB Correct.
4 Correct 206 ms 11232 KB Correct.
5 Correct 351 ms 18996 KB Correct.
6 Correct 166 ms 10440 KB Correct.
7 Correct 236 ms 11888 KB Correct.
8 Correct 149 ms 4080 KB Correct.
9 Correct 85 ms 3288 KB Correct.
10 Correct 72 ms 3172 KB Correct.
11 Correct 118 ms 3372 KB Correct.
12 Correct 95 ms 3348 KB Correct.
13 Correct 82 ms 3244 KB Correct.
14 Correct 260 ms 20636 KB Correct.
15 Correct 237 ms 7552 KB Correct.
16 Correct 87 ms 3232 KB Correct.
17 Correct 92 ms 3156 KB Correct.
18 Correct 86 ms 3224 KB Correct.
19 Correct 148 ms 3116 KB Correct.
20 Correct 8 ms 2896 KB Correct.
21 Correct 10 ms 3028 KB Correct.
22 Correct 14 ms 3540 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 3240 KB Correct.
2 Correct 22 ms 3328 KB Correct.
3 Incorrect 462 ms 40716 KB Wrong Answer.
4 Halted 0 ms 0 KB -