oj.uz

Submission #1080855

# Submission time Handle Problem Language Result Execution time Memory
1080855 2024-08-29T15:09:50 Z Muhammet Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 112252 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)), vis(n+1, vector<lb> (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){
                lb 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}});
            }
        }
    }

    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 28 ms 964 KB Correct.
2 Correct 25 ms 712 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2396 KB Correct.
2 Correct 46 ms 2708 KB Correct.
3 Correct 29 ms 2596 KB Correct.
4 Correct 43 ms 2616 KB Correct.
5 Correct 32 ms 2572 KB Correct.
6 Correct 33 ms 12460 KB Correct.
7 Correct 39 ms 12380 KB Correct.
8 Correct 38 ms 23644 KB Correct.
9 Correct 25 ms 1372 KB Correct.
10 Correct 41 ms 1360 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2720 KB Correct.
2 Correct 36 ms 2408 KB Correct.
3 Correct 31 ms 2544 KB Correct.
4 Correct 26 ms 1380 KB Correct.
5 Correct 27 ms 1360 KB Correct.
6 Correct 11 ms 9816 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 68900 KB Correct.
2 Correct 999 ms 2504 KB Correct.
3 Correct 876 ms 2696 KB Correct.
4 Correct 898 ms 2532 KB Correct.
5 Correct 736 ms 1472 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2492 KB Correct.
2 Correct 27 ms 2516 KB Correct.
3 Correct 28 ms 2580 KB Correct.
4 Correct 27 ms 12024 KB Correct.
5 Correct 23 ms 1368 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2592 KB Correct.
2 Correct 29 ms 2396 KB Correct.
3 Correct 63 ms 89684 KB Correct.
4 Correct 24 ms 7800 KB Correct.
5 Correct 26 ms 1372 KB Correct.
6 Correct 39 ms 2468 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 5240 KB Correct.
2 Correct 93 ms 4472 KB Correct.
3 Correct 2959 ms 75832 KB Correct.
4 Correct 2429 ms 21848 KB Correct.
5 Correct 2410 ms 112252 KB Correct.
6 Correct 862 ms 51612 KB Correct.
7 Correct 2280 ms 20844 KB Correct.
8 Correct 2109 ms 5204 KB Correct.
9 Correct 734 ms 4372 KB Correct.
10 Correct 729 ms 5032 KB Correct.
11 Correct 2073 ms 3480 KB Correct.
12 Correct 779 ms 4068 KB Correct.
13 Correct 755 ms 5472 KB Correct.
14 Correct 1873 ms 23304 KB Correct.
15 Correct 2432 ms 10444 KB Correct.
16 Correct 713 ms 4160 KB Correct.
17 Correct 956 ms 4108 KB Correct.
18 Correct 945 ms 4100 KB Correct.
19 Correct 2771 ms 6480 KB Correct.
20 Correct 48 ms 788 KB Correct.
21 Correct 64 ms 2324 KB Correct.
22 Correct 69 ms 6344 KB Correct.

Subtask #8
0.0 / 3.0

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