oj.uz

Submission #1081557

# Submission time Handle Problem Language Result Execution time Memory
1081557 2024-08-30T07:19:37 Z Muhammet Cyberland (APIO23_cyberland) C++17
68 / 100
 801 ms 120948 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,66);

    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+1,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 j = 0; j < n; j++){
            dis[j][i] = min(dis[j][i],dis[j][i-1]);
        }
    }

    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 38 ms 852 KB Correct.
2 Correct 37 ms 728 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1616 KB Correct.
2 Correct 177 ms 2036 KB Correct.
3 Correct 194 ms 1804 KB Correct.
4 Correct 175 ms 2100 KB Correct.
5 Correct 171 ms 2088 KB Correct.
6 Correct 272 ms 7384 KB Correct.
7 Correct 354 ms 7248 KB Correct.
8 Correct 169 ms 13400 KB Correct.
9 Correct 126 ms 1112 KB Correct.
10 Correct 124 ms 1108 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 1732 KB Correct.
2 Correct 234 ms 1660 KB Correct.
3 Correct 198 ms 1720 KB Correct.
4 Correct 154 ms 1080 KB Correct.
5 Correct 164 ms 1108 KB Correct.
6 Correct 75 ms 5720 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 37968 KB Correct.
2 Correct 95 ms 1876 KB Correct.
3 Correct 90 ms 1868 KB Correct.
4 Correct 86 ms 1776 KB Correct.
5 Correct 84 ms 1108 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1612 KB Correct.
2 Correct 113 ms 2068 KB Correct.
3 Correct 121 ms 1764 KB Correct.
4 Correct 190 ms 6652 KB Correct.
5 Correct 75 ms 1104 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 1816 KB Correct.
2 Correct 104 ms 1792 KB Correct.
3 Correct 95 ms 49720 KB Correct.
4 Correct 136 ms 4616 KB Correct.
5 Correct 96 ms 1104 KB Correct.
6 Correct 122 ms 1812 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 1596 KB Correct.
2 Correct 24 ms 1372 KB Correct.
3 Incorrect 745 ms 42836 KB Wrong Answer.
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 2168 KB Correct.
2 Correct 45 ms 2396 KB Correct.
3 Incorrect 801 ms 120948 KB Wrong Answer.
4 Halted 0 ms 0 KB -