oj.uz

Submission #1081415

# Submission time Handle Problem Language Result Execution time Memory
1081415 2024-08-30T04:22:02 Z Muhammet Cyberland (APIO23_cyberland) C++17
40 / 100
 931 ms 48156 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];

    ll s = 0;
    for(auto i : c){
        s += i;
    }

    k = min(k,(int)log2(s));

    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]});
    }
    priority_queue <pair<lb,pair<ll,ll>>> q;
    q.push({0,{0,0}});
    vector <vector<lb>> dis(n+1, vector<lb> (k+1,1e18));
    dis[0][0] = 0;
    while(!q.empty()){
        auto [w,x] = q.top();
        q.pop();
        if(-w != dis[x.ff][x.ss]) continue;
        if(x.ff == h) continue;
        for(auto [to,w1] : v[x.ff]){
            if(a[to] == 2 and x.ss < k){
                lb w2 = w1;
                if((dis[x.ff][x.ss] + w2) / 2 < dis[to][x.ss+1]){
                    dis[to][x.ss+1] = (dis[x.ff][x.ss] + w2) / 2;
                    q.push({-dis[to][x.ss+1],{to,x.ss+1}});
                }
            }
            if((dis[to][x.ss] > dis[x.ff][x.ss] + w1) or (a[to] == 0 and dis[to][x.ss] != 0)){
                dis[to][x.ss] = dis[x.ff][x.ss] + w1;
                if(a[to] == 0) dis[to][x.ss] = 0;
                q.push({-dis[to][x.ss],{to,x.ss}});
            }
        }
    }

    lb ans = 1e18;
    for(int i = 0; i <= k; i++){
        ans = min(ans,dis[h][i]);
    }
    
    if(ans == 1e18) return -1;

    return ans;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1116 KB Correct.
2 Correct 26 ms 1012 KB Correct.
3 Correct 24 ms 1080 KB Correct.
4 Correct 25 ms 1108 KB Correct.
5 Correct 25 ms 1072 KB Correct.
6 Correct 26 ms 6628 KB Correct.
7 Correct 31 ms 6492 KB Correct.
8 Correct 16 ms 12892 KB Correct.
9 Correct 21 ms 348 KB Correct.
10 Correct 21 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 860 KB Correct.
2 Correct 29 ms 1036 KB Correct.
3 Correct 25 ms 1116 KB Correct.
4 Correct 23 ms 568 KB Correct.
5 Correct 24 ms 344 KB Correct.
6 Correct 7 ms 5468 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 36948 KB Correct.
2 Correct 931 ms 1088 KB Correct.
3 Correct 790 ms 1132 KB Correct.
4 Correct 861 ms 1068 KB Correct.
5 Correct 692 ms 752 KB Correct.

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1052 KB Correct.
2 Correct 25 ms 1048 KB Correct.
3 Correct 29 ms 1092 KB Correct.
4 Correct 24 ms 6392 KB Correct.
5 Runtime error 3 ms 604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1100 KB Correct.
2 Correct 25 ms 1028 KB Correct.
3 Correct 50 ms 48156 KB Correct.
4 Correct 24 ms 4304 KB Correct.
5 Runtime error 8 ms 856 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 362 ms 3132 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 542 ms 2864 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -