oj.uz

Submission #1081412

# Submission time Handle Problem Language Result Execution time Memory
1081412 2024-08-30T04:15:42 Z Muhammet Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 91796 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 604 KB Correct.
2 Correct 21 ms 524 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1116 KB Correct.
2 Correct 26 ms 1096 KB Correct.
3 Correct 23 ms 1104 KB Correct.
4 Correct 25 ms 1112 KB Correct.
5 Correct 27 ms 1128 KB Correct.
6 Correct 25 ms 6628 KB Correct.
7 Correct 32 ms 6604 KB Correct.
8 Correct 18 ms 12756 KB Correct.
9 Correct 22 ms 348 KB Correct.
10 Correct 20 ms 348 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 1036 KB Correct.
3 Correct 25 ms 1116 KB Correct.
4 Correct 23 ms 568 KB Correct.
5 Correct 23 ms 344 KB Correct.
6 Correct 8 ms 5428 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 36956 KB Correct.
2 Correct 912 ms 1092 KB Correct.
3 Correct 785 ms 1132 KB Correct.
4 Correct 853 ms 1088 KB Correct.
5 Correct 689 ms 760 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1056 KB Correct.
2 Correct 24 ms 1044 KB Correct.
3 Correct 24 ms 1092 KB Correct.
4 Correct 26 ms 6388 KB Correct.
5 Correct 19 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1096 KB Correct.
2 Correct 23 ms 1044 KB Correct.
3 Correct 49 ms 48212 KB Correct.
4 Correct 19 ms 4288 KB Correct.
5 Correct 20 ms 348 KB Correct.
6 Correct 24 ms 1200 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 3848 KB Correct.
2 Correct 93 ms 3976 KB Correct.
3 Correct 2517 ms 42964 KB Correct.
4 Correct 2173 ms 11348 KB Correct.
5 Correct 2066 ms 91796 KB Correct.
6 Correct 729 ms 44720 KB Correct.
7 Correct 2079 ms 11684 KB Correct.
8 Correct 2001 ms 2484 KB Correct.
9 Correct 660 ms 3076 KB Correct.
10 Correct 712 ms 3896 KB Correct.
11 Correct 1968 ms 1740 KB Correct.
12 Correct 719 ms 2744 KB Correct.
13 Correct 708 ms 4016 KB Correct.
14 Correct 1636 ms 14820 KB Correct.
15 Correct 2285 ms 5448 KB Correct.
16 Correct 657 ms 2972 KB Correct.
17 Correct 848 ms 2716 KB Correct.
18 Correct 839 ms 2700 KB Correct.
19 Correct 2535 ms 4000 KB Correct.
20 Correct 45 ms 724 KB Correct.
21 Correct 54 ms 1888 KB Correct.
22 Correct 59 ms 6592 KB Correct.

Subtask #8
0.0 / 3.0

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