oj.uz

Submission #1081563

# Submission time Handle Problem Language Result Execution time Memory
1081563 2024-08-30T07:26:28 Z Muhammet Cyberland (APIO23_cyberland) C++17
100 / 100
 1965 ms 129768 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
// #include "stub.cpp"

using namespace std;

#define lb long double
#define ll long long

#define ff first
#define ss second

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
    vector <pair<ll, ll>> v[n+5];

    k = min(k,70);

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

    vector <vector<lb>> dis(n+1, vector<lb> (k+2,1e18));
    priority_queue <pair<lb,ll>> q;

    q.push({0,0});
    dis[0][0] = 0;
    while(!q.empty()){
        auto [w,x] = q.top();
        q.pop();
        w *= -1;
        if(w != dis[x][0]) continue;
        if(x == h) continue;
        for(auto [to,w1] : v[x]){
            if((dis[to][0] > dis[x][0] + w1) or (a[to] == 0 and dis[to][0] != 0)){
                dis[to][0] = dis[x][0] + w1;
                if(a[to] == 0) dis[to][0] = 0;
                q.push({-dis[to][0],to});
            }
        }
    }

    lb ans = 1e18;
    bool tr = 0;

    for(int i = 1; i <= k; i++){
        q.push({0,0});
        dis[0][i] = 0;
        while(!q.empty()){
            auto [w,x] = q.top();
            q.pop();
            w *= -1;
            if(w != dis[x][i]) continue;
            if(x == h) continue;
            for(auto [to,w1] : v[x]){
                if(a[to] == 2){
                    lb w2 = w1;
                    if(dis[to][i] > (dis[x][i-1] + w2) / 2){
                        dis[to][i] = (dis[x][i-1] + w2) / 2;
                        q.push({-dis[to][i],to});
                    }
                }
                if((dis[to][i] > dis[x][i] + w1) or (a[to] == 0 and dis[to][i] != 0)){
                    dis[to][i] = dis[x][i] + w1;
                    if(a[to] == 0) dis[to][i] = 0;
                    q.push({-dis[to][i],to});
                }
            }
        }
    }

    for(int i = 0; i <= k; i++){
        ans = min(ans, dis[h][i]);
    }

    if(ans == 1e18) return -1;

    return ans;
}

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:44:10: warning: unused variable 'tr' [-Wunused-variable]
   44 |     bool tr = 0;
      |          ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 848 KB Correct.
2 Correct 34 ms 864 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 1872 KB Correct.
2 Correct 170 ms 2128 KB Correct.
3 Correct 159 ms 1976 KB Correct.
4 Correct 173 ms 1932 KB Correct.
5 Correct 168 ms 2184 KB Correct.
6 Correct 265 ms 7476 KB Correct.
7 Correct 361 ms 7504 KB Correct.
8 Correct 178 ms 13656 KB Correct.
9 Correct 120 ms 1320 KB Correct.
10 Correct 119 ms 1364 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 1912 KB Correct.
2 Correct 216 ms 1984 KB Correct.
3 Correct 201 ms 1964 KB Correct.
4 Correct 165 ms 1360 KB Correct.
5 Correct 150 ms 1292 KB Correct.
6 Correct 75 ms 5724 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 39208 KB Correct.
2 Correct 83 ms 1920 KB Correct.
3 Correct 76 ms 2068 KB Correct.
4 Correct 81 ms 2008 KB Correct.
5 Correct 74 ms 1360 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 1864 KB Correct.
2 Correct 99 ms 2080 KB Correct.
3 Correct 108 ms 2072 KB Correct.
4 Correct 194 ms 7160 KB Correct.
5 Correct 76 ms 1364 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 1980 KB Correct.
2 Correct 100 ms 1956 KB Correct.
3 Correct 51 ms 51268 KB Correct.
4 Correct 136 ms 4940 KB Correct.
5 Correct 90 ms 1300 KB Correct.
6 Correct 113 ms 1980 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 1888 KB Correct.
2 Correct 24 ms 1372 KB Correct.
3 Correct 717 ms 45132 KB Correct.
4 Correct 472 ms 13476 KB Correct.
5 Correct 768 ms 29640 KB Correct.
6 Correct 370 ms 14036 KB Correct.
7 Correct 497 ms 12468 KB Correct.
8 Correct 327 ms 3884 KB Correct.
9 Correct 125 ms 1952 KB Correct.
10 Correct 126 ms 1864 KB Correct.
11 Correct 271 ms 2792 KB Correct.
12 Correct 144 ms 2016 KB Correct.
13 Correct 136 ms 2004 KB Correct.
14 Correct 432 ms 14644 KB Correct.
15 Correct 428 ms 6232 KB Correct.
16 Correct 131 ms 2112 KB Correct.
17 Correct 155 ms 2072 KB Correct.
18 Correct 149 ms 1980 KB Correct.
19 Correct 417 ms 2864 KB Correct.
20 Correct 9 ms 604 KB Correct.
21 Correct 10 ms 1084 KB Correct.
22 Correct 24 ms 1704 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 2472 KB Correct.
2 Correct 45 ms 2652 KB Correct.
3 Correct 728 ms 129768 KB Correct.
4 Correct 565 ms 6852 KB Correct.
5 Correct 1742 ms 51792 KB Correct.
6 Correct 823 ms 20436 KB Correct.
7 Correct 883 ms 25896 KB Correct.
8 Correct 417 ms 4024 KB Correct.
9 Correct 251 ms 2728 KB Correct.
10 Correct 250 ms 2484 KB Correct.
11 Correct 305 ms 1872 KB Correct.
12 Correct 268 ms 2736 KB Correct.
13 Correct 273 ms 2580 KB Correct.
14 Correct 1965 ms 52560 KB Correct.
15 Correct 1731 ms 65200 KB Correct.
16 Correct 805 ms 22884 KB Correct.
17 Correct 474 ms 6548 KB Correct.
18 Correct 256 ms 2720 KB Correct.
19 Correct 316 ms 2756 KB Correct.
20 Correct 305 ms 2684 KB Correct.
21 Correct 806 ms 3668 KB Correct.
22 Correct 18 ms 604 KB Correct.
23 Correct 21 ms 1552 KB Correct.
24 Correct 53 ms 2384 KB Correct.