oj.uz

Submission #1080803

# Submission time Handle Problem Language Result Execution time Memory
1080803 2024-08-29T14:26:42 Z Muhammet Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 112200 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
// #include "stub.cpp"

using namespace std;

#define ll long double

#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<long long, long long>> v[n+5];

    k = min(k,70);

    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<ll,pair<long long,long long>>> q;
    q.push({0,{0,0}});
    vector <vector<ll>> dis(n+1, vector<ll> (k+1,1e18)), vis(n+1, vector<ll> (k+1,1e18));
    dis[0][0] = 0;
    vis[0][0] = 0;
    while(!q.empty()){
        auto [w,x] = q.top();
        q.pop();
        vis[x.ff][x.ss] = 1;
        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){
                ll w2 = w1;
                if(vis[to][x.ss+1] == 0 or (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) or (vis[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}});
            }
        }
    }

    ll 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 23 ms 864 KB Correct.
2 Correct 23 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2392 KB Correct.
2 Correct 33 ms 2584 KB Correct.
3 Correct 26 ms 2640 KB Correct.
4 Correct 28 ms 2648 KB Correct.
5 Correct 32 ms 2572 KB Correct.
6 Correct 34 ms 12440 KB Correct.
7 Correct 39 ms 12380 KB Correct.
8 Correct 30 ms 23640 KB Correct.
9 Correct 23 ms 1396 KB Correct.
10 Correct 25 ms 1372 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2484 KB Correct.
2 Correct 35 ms 2404 KB Correct.
3 Correct 28 ms 2532 KB Correct.
4 Correct 28 ms 1484 KB Correct.
5 Correct 38 ms 1516 KB Correct.
6 Correct 9 ms 9816 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 68844 KB Correct.
2 Correct 998 ms 2532 KB Correct.
3 Correct 876 ms 2732 KB Correct.
4 Correct 892 ms 2528 KB Correct.
5 Correct 715 ms 1764 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2604 KB Correct.
2 Correct 26 ms 2516 KB Correct.
3 Correct 27 ms 2572 KB Correct.
4 Correct 29 ms 12020 KB Correct.
5 Correct 22 ms 1368 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2528 KB Correct.
2 Correct 27 ms 2396 KB Correct.
3 Correct 72 ms 89680 KB Correct.
4 Correct 23 ms 7804 KB Correct.
5 Correct 25 ms 1368 KB Correct.
6 Correct 28 ms 2468 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 5136 KB Correct.
2 Correct 96 ms 4416 KB Correct.
3 Correct 2838 ms 76052 KB Correct.
4 Correct 2250 ms 21912 KB Correct.
5 Correct 2267 ms 112200 KB Correct.
6 Correct 804 ms 51612 KB Correct.
7 Correct 2189 ms 20756 KB Correct.
8 Correct 2086 ms 5352 KB Correct.
9 Correct 699 ms 4248 KB Correct.
10 Correct 719 ms 5040 KB Correct.
11 Correct 2012 ms 3600 KB Correct.
12 Correct 754 ms 4296 KB Correct.
13 Correct 759 ms 5544 KB Correct.
14 Correct 1728 ms 24080 KB Correct.
15 Correct 2388 ms 10384 KB Correct.
16 Correct 681 ms 4292 KB Correct.
17 Correct 896 ms 4116 KB Correct.
18 Correct 909 ms 4432 KB Correct.
19 Correct 2633 ms 6488 KB Correct.
20 Correct 46 ms 800 KB Correct.
21 Correct 56 ms 2324 KB Correct.
22 Correct 63 ms 6400 KB Correct.

Subtask #8
0.0 / 3.0

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