oj.uz

Submission #1081413

# Submission time Handle Problem Language Result Execution time Memory
1081413 2024-08-30T04:17:01 Z Muhammet Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 91792 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,64);

    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 600 KB Correct.
2 Correct 21 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1112 KB Correct.
2 Correct 25 ms 1116 KB Correct.
3 Correct 25 ms 1116 KB Correct.
4 Correct 25 ms 1116 KB Correct.
5 Correct 26 ms 1112 KB Correct.
6 Correct 26 ms 6628 KB Correct.
7 Correct 34 ms 6488 KB Correct.
8 Correct 21 ms 12892 KB Correct.
9 Correct 22 ms 348 KB Correct.
10 Correct 22 ms 572 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 860 KB Correct.
2 Correct 31 ms 1140 KB Correct.
3 Correct 27 ms 1112 KB Correct.
4 Correct 24 ms 344 KB Correct.
5 Correct 23 ms 540 KB Correct.
6 Correct 7 ms 5464 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 36956 KB Correct.
2 Correct 921 ms 1092 KB Correct.
3 Correct 774 ms 1136 KB Correct.
4 Correct 849 ms 1076 KB Correct.
5 Correct 686 ms 604 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1052 KB Correct.
2 Correct 25 ms 1096 KB Correct.
3 Correct 23 ms 1092 KB Correct.
4 Correct 24 ms 6388 KB Correct.
5 Correct 23 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1088 KB Correct.
2 Correct 22 ms 1028 KB Correct.
3 Correct 50 ms 48292 KB Correct.
4 Correct 20 ms 4220 KB Correct.
5 Correct 22 ms 348 KB Correct.
6 Correct 25 ms 1076 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 3892 KB Correct.
2 Correct 87 ms 3908 KB Correct.
3 Correct 2508 ms 42948 KB Correct.
4 Correct 2199 ms 11352 KB Correct.
5 Correct 2016 ms 91792 KB Correct.
6 Correct 690 ms 44596 KB Correct.
7 Correct 2078 ms 11908 KB Correct.
8 Correct 2045 ms 2472 KB Correct.
9 Correct 663 ms 2936 KB Correct.
10 Correct 706 ms 3916 KB Correct.
11 Correct 1966 ms 1892 KB Correct.
12 Correct 707 ms 2676 KB Correct.
13 Correct 701 ms 4120 KB Correct.
14 Correct 1644 ms 15912 KB Correct.
15 Correct 2260 ms 5488 KB Correct.
16 Correct 641 ms 2716 KB Correct.
17 Correct 854 ms 2992 KB Correct.
18 Correct 837 ms 2836 KB Correct.
19 Correct 2513 ms 4024 KB Correct.
20 Correct 44 ms 976 KB Correct.
21 Correct 54 ms 2064 KB Correct.
22 Correct 60 ms 7620 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3031 ms 13960 KB Time limit exceeded
2 Halted 0 ms 0 KB -