oj.uz

Submission #1080859

# Submission time Handle Problem Language Result Execution time Memory
1080859 2024-08-29T15:11:34 Z Muhammet Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 91768 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]});
    }
    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 20 ms 596 KB Correct.
2 Correct 21 ms 544 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1096 KB Correct.
2 Correct 26 ms 1112 KB Correct.
3 Correct 23 ms 1116 KB Correct.
4 Correct 25 ms 1116 KB Correct.
5 Correct 26 ms 1092 KB Correct.
6 Correct 24 ms 6624 KB Correct.
7 Correct 33 ms 6492 KB Correct.
8 Correct 18 ms 12892 KB Correct.
9 Correct 26 ms 344 KB Correct.
10 Correct 23 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 856 KB Correct.
2 Correct 29 ms 1028 KB Correct.
3 Correct 27 ms 1112 KB Correct.
4 Correct 23 ms 348 KB Correct.
5 Correct 24 ms 580 KB Correct.
6 Correct 7 ms 5468 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 36776 KB Correct.
2 Correct 916 ms 1188 KB Correct.
3 Correct 777 ms 1152 KB Correct.
4 Correct 884 ms 1076 KB Correct.
5 Correct 689 ms 604 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1052 KB Correct.
2 Correct 24 ms 1048 KB Correct.
3 Correct 24 ms 1092 KB Correct.
4 Correct 32 ms 6392 KB Correct.
5 Correct 19 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1064 KB Correct.
2 Correct 30 ms 1004 KB Correct.
3 Correct 50 ms 48212 KB Correct.
4 Correct 19 ms 4288 KB Correct.
5 Correct 21 ms 348 KB Correct.
6 Correct 34 ms 1076 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 3836 KB Correct.
2 Correct 92 ms 4036 KB Correct.
3 Correct 2489 ms 43004 KB Correct.
4 Correct 2168 ms 11228 KB Correct.
5 Correct 2113 ms 91768 KB Correct.
6 Correct 753 ms 44564 KB Correct.
7 Correct 2196 ms 11604 KB Correct.
8 Correct 2129 ms 2652 KB Correct.
9 Correct 707 ms 2888 KB Correct.
10 Correct 777 ms 3768 KB Correct.
11 Correct 2049 ms 1744 KB Correct.
12 Correct 760 ms 2680 KB Correct.
13 Correct 814 ms 4148 KB Correct.
14 Correct 1955 ms 14816 KB Correct.
15 Correct 2600 ms 5692 KB Correct.
16 Correct 721 ms 2688 KB Correct.
17 Correct 985 ms 2736 KB Correct.
18 Correct 902 ms 2732 KB Correct.
19 Correct 2977 ms 4124 KB Correct.
20 Correct 47 ms 728 KB Correct.
21 Correct 60 ms 2100 KB Correct.
22 Correct 61 ms 5836 KB Correct.

Subtask #8
0.0 / 3.0

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