oj.uz

Submission #753049

# Submission time Handle Problem Language Result Execution time Memory
753049 2023-06-04T13:50:40 Z MohamedFaresNebili Cyberland (APIO23_cyberland) C++17
100 / 100
 1606 ms 64504 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

        using namespace std;
        using ll = long long;
        using pi = pair<double, pair<int, int>>;

        const ll M = 1000000000000000005;
        const double epsilon = 0.000001;

        double solve(int n, int m, int k, int h, vector<int> x,
                     vector<int> y, vector<int> c, vector<int> arr) {
            k = min(k, 70);
            double d[n][k + 1];
            for(int l = 0; l < n; l++)
                for(int i = 0; i <= k; i++)
                    d[l][i] = M;
            vector<pair<int, int>> adj[n]; d[0][0] = 0;
            for(int l = 0; l < m; l++) {
                adj[x[l]].push_back({y[l], c[l]});
                adj[y[l]].push_back({x[l], c[l]});
            }
            queue<int> q; vector<bool> vis(n, 0);
            vis[0] = 1; q.push(0);
            while(!q.empty()) {
                int u = q.front(); q.pop();
                if(arr[u] == 0) d[u][0] = 0;
                if(u == h) continue;
                for(auto v : adj[u]) {
                    if(vis[v.first]) continue;
                    vis[v.first] = 1; q.push(v.first);
                }
            }

            for(int l = 0; l <= k; l++) {
                priority_queue<pair<double, int>, vector<pair<double, int>>,
                greater<pair<double, int>>> pq;
                for(int i = 0; i < n; i++)
                    if(i != h && d[i][l] != M)
                        pq.push({d[i][l], i});
                while(!pq.empty()) {
                    double w = pq.top().first;
                    int u = pq.top().second; pq.pop();
                    if(u == h) continue;
                    for(auto v : adj[u]) {
                        if(arr[v.first] == 2 && l < k)
                            d[v.first][l + 1] = min(d[v.first][l + 1], (d[u][l] + v.second) / 2.0);
                        if(d[u][l] + v.second < d[v.first][l]) {
                            d[v.first][l] = d[u][l] + v.second;
                            pq.push({d[v.first][l], v.first});
                        }
                    }
                }
            }

            double res = M;
            for(int l = 0; l <= k; l++)
                res = min(res, d[h][l]);
            if(res == M) return -1;
            return res;
        }

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:43:28: warning: unused variable 'w' [-Wunused-variable]
   43 |                     double w = pq.top().first;
      |                            ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 340 KB Correct.
2 Correct 38 ms 368 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 656 KB Correct.
2 Correct 37 ms 692 KB Correct.
3 Correct 37 ms 596 KB Correct.
4 Correct 33 ms 596 KB Correct.
5 Correct 34 ms 652 KB Correct.
6 Correct 32 ms 3548 KB Correct.
7 Correct 41 ms 3532 KB Correct.
8 Correct 19 ms 6920 KB Correct.
9 Correct 31 ms 372 KB Correct.
10 Correct 30 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 676 KB Correct.
2 Correct 34 ms 680 KB Correct.
3 Correct 32 ms 720 KB Correct.
4 Correct 33 ms 340 KB Correct.
5 Correct 34 ms 376 KB Correct.
6 Correct 7 ms 3156 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 19652 KB Correct.
2 Correct 137 ms 652 KB Correct.
3 Correct 117 ms 648 KB Correct.
4 Correct 123 ms 676 KB Correct.
5 Correct 88 ms 460 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 684 KB Correct.
2 Correct 35 ms 584 KB Correct.
3 Correct 32 ms 724 KB Correct.
4 Correct 29 ms 3540 KB Correct.
5 Correct 26 ms 380 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 680 KB Correct.
2 Correct 26 ms 596 KB Correct.
3 Correct 65 ms 25556 KB Correct.
4 Correct 20 ms 2788 KB Correct.
5 Correct 30 ms 376 KB Correct.
6 Correct 29 ms 660 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 660 KB Correct.
2 Correct 24 ms 852 KB Correct.
3 Correct 722 ms 22712 KB Correct.
4 Correct 321 ms 5892 KB Correct.
5 Correct 735 ms 15344 KB Correct.
6 Correct 326 ms 7428 KB Correct.
7 Correct 320 ms 6080 KB Correct.
8 Correct 246 ms 1452 KB Correct.
9 Correct 140 ms 756 KB Correct.
10 Correct 140 ms 636 KB Correct.
11 Correct 241 ms 740 KB Correct.
12 Correct 148 ms 596 KB Correct.
13 Correct 152 ms 816 KB Correct.
14 Correct 305 ms 7360 KB Correct.
15 Correct 266 ms 2532 KB Correct.
16 Correct 149 ms 612 KB Correct.
17 Correct 168 ms 704 KB Correct.
18 Correct 162 ms 644 KB Correct.
19 Correct 383 ms 628 KB Correct.
20 Correct 11 ms 340 KB Correct.
21 Correct 11 ms 592 KB Correct.
22 Correct 27 ms 980 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 992 KB Correct.
2 Correct 51 ms 1364 KB Correct.
3 Correct 789 ms 64504 KB Correct.
4 Correct 342 ms 3000 KB Correct.
5 Correct 1422 ms 26388 KB Correct.
6 Correct 774 ms 10676 KB Correct.
7 Correct 596 ms 13592 KB Correct.
8 Correct 358 ms 1376 KB Correct.
9 Correct 288 ms 1044 KB Correct.
10 Correct 274 ms 948 KB Correct.
11 Correct 248 ms 576 KB Correct.
12 Correct 303 ms 968 KB Correct.
13 Correct 317 ms 1072 KB Correct.
14 Correct 1606 ms 26888 KB Correct.
15 Correct 1234 ms 32284 KB Correct.
16 Correct 501 ms 11044 KB Correct.
17 Correct 355 ms 2704 KB Correct.
18 Correct 288 ms 1016 KB Correct.
19 Correct 345 ms 1008 KB Correct.
20 Correct 326 ms 908 KB Correct.
21 Correct 794 ms 944 KB Correct.
22 Correct 20 ms 340 KB Correct.
23 Correct 21 ms 868 KB Correct.
24 Correct 56 ms 1236 KB Correct.