oj.uz

Submission #750555

# Submission time Handle Problem Language Result Execution time Memory
750555 2023-05-29T17:23:11 Z arnold518 Cyberland (APIO23_cyberland) C++17
100 / 100
 1534 ms 126828 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][150], P[150];
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, 120);

    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 21 ms 2780 KB Correct.
2 Correct 20 ms 2832 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3924 KB Correct.
2 Correct 28 ms 3908 KB Correct.
3 Correct 26 ms 3968 KB Correct.
4 Correct 26 ms 3924 KB Correct.
5 Correct 26 ms 3952 KB Correct.
6 Correct 26 ms 14892 KB Correct.
7 Correct 39 ms 14676 KB Correct.
8 Correct 24 ms 27112 KB Correct.
9 Correct 24 ms 2772 KB Correct.
10 Correct 23 ms 2840 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3924 KB Correct.
2 Correct 22 ms 3936 KB Correct.
3 Correct 20 ms 3924 KB Correct.
4 Correct 23 ms 2772 KB Correct.
5 Correct 24 ms 2772 KB Correct.
6 Correct 9 ms 12608 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 74876 KB Correct.
2 Correct 72 ms 3948 KB Correct.
3 Correct 68 ms 3944 KB Correct.
4 Correct 65 ms 3924 KB Correct.
5 Correct 76 ms 2908 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4000 KB Correct.
2 Correct 27 ms 4036 KB Correct.
3 Correct 26 ms 4044 KB Correct.
4 Correct 36 ms 14892 KB Correct.
5 Correct 23 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4024 KB Correct.
2 Correct 27 ms 4016 KB Correct.
3 Correct 82 ms 96944 KB Correct.
4 Correct 25 ms 11444 KB Correct.
5 Correct 24 ms 2824 KB Correct.
6 Correct 22 ms 4020 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 4088 KB Correct.
2 Correct 21 ms 4844 KB Correct.
3 Correct 567 ms 121200 KB Correct.
4 Correct 223 ms 29608 KB Correct.
5 Correct 400 ms 49572 KB Correct.
6 Correct 179 ms 19388 KB Correct.
7 Correct 251 ms 32328 KB Correct.
8 Correct 145 ms 7100 KB Correct.
9 Correct 81 ms 4104 KB Correct.
10 Correct 72 ms 4060 KB Correct.
11 Correct 115 ms 4272 KB Correct.
12 Correct 88 ms 4016 KB Correct.
13 Correct 80 ms 4004 KB Correct.
14 Correct 285 ms 60412 KB Correct.
15 Correct 220 ms 18184 KB Correct.
16 Correct 87 ms 4048 KB Correct.
17 Correct 86 ms 3968 KB Correct.
18 Correct 81 ms 4080 KB Correct.
19 Correct 145 ms 3924 KB Correct.
20 Correct 9 ms 2772 KB Correct.
21 Correct 10 ms 3796 KB Correct.
22 Correct 16 ms 4308 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 4404 KB Correct.
2 Correct 65 ms 5616 KB Correct.
3 Correct 1534 ms 126828 KB Correct.
4 Correct 324 ms 10568 KB Correct.
5 Correct 1192 ms 53380 KB Correct.
6 Correct 452 ms 26936 KB Correct.
7 Correct 669 ms 47164 KB Correct.
8 Correct 213 ms 4524 KB Correct.
9 Correct 242 ms 4336 KB Correct.
10 Correct 211 ms 4452 KB Correct.
11 Correct 288 ms 2920 KB Correct.
12 Correct 268 ms 4480 KB Correct.
13 Correct 237 ms 4372 KB Correct.
14 Correct 1454 ms 52424 KB Correct.
15 Correct 1476 ms 64264 KB Correct.
16 Correct 445 ms 24776 KB Correct.
17 Correct 284 ms 7168 KB Correct.
18 Correct 263 ms 4380 KB Correct.
19 Correct 256 ms 4416 KB Correct.
20 Correct 226 ms 4412 KB Correct.
21 Correct 442 ms 4364 KB Correct.
22 Correct 22 ms 2772 KB Correct.
23 Correct 26 ms 4108 KB Correct.
24 Correct 33 ms 4816 KB Correct.