oj.uz

Submission #764295

# Submission time Handle Problem Language Result Execution time Memory
764295 2023-06-23T10:14:39 Z PoonYaPat Cyberland (APIO23_cyberland) C++17
100 / 100
 426 ms 263196 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef pair<int,ld> pii;

struct NN {
    ld d;
    int node,half;
    bool zer;
    bool operator < (const NN &o) const {return d>o.d;}
};

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    int n=N,m=M,k=min(K,70),st=H;
    vector<pii> adj[n];
    ld dis[n][k+5][2];
    bool vis[n][k+5][2];
    for (int i=0; i<n; ++i) for (int j=0; j<=k; ++j) dis[i][j][0]=DBL_MAX, dis[i][j][1]=DBL_MAX, vis[i][j][0]=false, vis[i][j][1]=false;

    for (int i=0; i<m; ++i) {
        adj[x[i]].push_back(pii(y[i],c[i]));
        adj[y[i]].push_back(pii(x[i],c[i]));
    }

    priority_queue<NN> q;
    dis[st][0][0]=0;
    q.push({dis[st][0][0],st,0,0});
    bool bef=false;

    while (!q.empty()) {
        int node=q.top().node, half=q.top().half;
        bool zer=q.top().zer;
        q.pop();

        if (vis[node][half][zer]) continue;
        vis[node][half][zer]=true;

        if (node==st) {
            if (!bef) bef=true;
            else continue;
        }
        if (node==0) return (double)(dis[node][half][zer]);

        for (auto s : adj[node]) {
            int des=s.first;
            ld w=s.second;

            if (zer==true) w=0;
            else w=w/pow(2,half);

            if (arr[node]==1) {
                if (dis[des][half][zer]>dis[node][half][zer]+w) {
                    dis[des][half][zer]=dis[node][half][zer]+w;
                    q.push({dis[des][half][zer],des,half,zer});
                }
            } else if (arr[node]==0) {
                if (dis[des][half][true]>dis[node][half][zer]) {
                    dis[des][half][true]=dis[node][half][zer];
                    q.push({dis[des][half][true],des,half,true});
                }
            } else {
                //don't use
                if (dis[des][half][zer]>dis[node][half][zer]+w) {
                    dis[des][half][zer]=dis[node][half][zer]+w;
                    q.push({dis[des][half][zer],des,half,zer});
                }

                //use
                if (half<k) {
                    if (dis[des][half+1][zer]>dis[node][half][zer]+w/2.0) {
                        dis[des][half+1][zer]=dis[node][half][zer]+w/2.0;
                        q.push({dis[des][half+1][zer],des,half+1,zer});
                    }
                }
            }

        }
    }
    return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 468 KB Correct.
2 Correct 20 ms 476 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1628 KB Correct.
2 Correct 35 ms 1612 KB Correct.
3 Correct 33 ms 1624 KB Correct.
4 Correct 34 ms 1628 KB Correct.
5 Correct 34 ms 1620 KB Correct.
6 Correct 31 ms 13012 KB Correct.
7 Correct 43 ms 12820 KB Correct.
8 Correct 25 ms 25812 KB Correct.
9 Correct 32 ms 472 KB Correct.
10 Correct 32 ms 468 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1500 KB Correct.
2 Correct 33 ms 1608 KB Correct.
3 Correct 32 ms 1640 KB Correct.
4 Correct 32 ms 464 KB Correct.
5 Correct 32 ms 468 KB Correct.
6 Correct 9 ms 10708 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 75880 KB Correct.
2 Correct 108 ms 1612 KB Correct.
3 Correct 68 ms 1684 KB Correct.
4 Correct 62 ms 1636 KB Correct.
5 Correct 97 ms 496 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1672 KB Correct.
2 Correct 36 ms 1680 KB Correct.
3 Correct 35 ms 1628 KB Correct.
4 Correct 34 ms 13112 KB Correct.
5 Correct 31 ms 476 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1620 KB Correct.
2 Correct 30 ms 1588 KB Correct.
3 Correct 103 ms 99532 KB Correct.
4 Correct 26 ms 9616 KB Correct.
5 Correct 33 ms 468 KB Correct.
6 Correct 32 ms 1656 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1892 KB Correct.
2 Correct 10 ms 2744 KB Correct.
3 Correct 108 ms 83480 KB Correct.
4 Correct 68 ms 21864 KB Correct.
5 Correct 78 ms 53340 KB Correct.
6 Correct 45 ms 23048 KB Correct.
7 Correct 70 ms 21824 KB Correct.
8 Correct 77 ms 4004 KB Correct.
9 Correct 58 ms 1876 KB Correct.
10 Correct 76 ms 1864 KB Correct.
11 Correct 66 ms 1716 KB Correct.
12 Correct 68 ms 1884 KB Correct.
13 Correct 58 ms 1984 KB Correct.
14 Correct 65 ms 24168 KB Correct.
15 Correct 62 ms 8260 KB Correct.
16 Correct 60 ms 2008 KB Correct.
17 Correct 62 ms 1864 KB Correct.
18 Correct 57 ms 2032 KB Correct.
19 Correct 162 ms 1748 KB Correct.
20 Correct 5 ms 468 KB Correct.
21 Correct 7 ms 1492 KB Correct.
22 Correct 5 ms 3024 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3440 KB Correct.
2 Correct 18 ms 5144 KB Correct.
3 Correct 232 ms 263196 KB Correct.
4 Correct 64 ms 10664 KB Correct.
5 Correct 118 ms 101696 KB Correct.
6 Correct 50 ms 37668 KB Correct.
7 Correct 84 ms 50912 KB Correct.
8 Correct 81 ms 4216 KB Correct.
9 Correct 108 ms 3448 KB Correct.
10 Correct 125 ms 3708 KB Correct.
11 Correct 426 ms 604 KB Correct.
12 Correct 129 ms 3720 KB Correct.
13 Correct 97 ms 3688 KB Correct.
14 Correct 111 ms 104408 KB Correct.
15 Correct 140 ms 130148 KB Correct.
16 Correct 87 ms 43840 KB Correct.
17 Correct 122 ms 9588 KB Correct.
18 Correct 116 ms 3804 KB Correct.
19 Correct 119 ms 3400 KB Correct.
20 Correct 93 ms 3460 KB Correct.
21 Correct 375 ms 3460 KB Correct.
22 Correct 10 ms 596 KB Correct.
23 Correct 14 ms 2772 KB Correct.
24 Correct 6 ms 4684 KB Correct.