oj.uz

Submission #1081410

# Submission time Handle Problem Language Result Execution time Memory
1081410 2024-08-30T04:14:36 Z Muhammet Cyberland (APIO23_cyberland) C++17
97 / 100
 2721 ms 110080 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,60);

    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 856 KB Correct.
2 Correct 21 ms 856 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1880 KB Correct.
2 Correct 29 ms 1884 KB Correct.
3 Correct 29 ms 1844 KB Correct.
4 Correct 26 ms 1840 KB Correct.
5 Correct 27 ms 1888 KB Correct.
6 Correct 25 ms 6628 KB Correct.
7 Correct 31 ms 6492 KB Correct.
8 Correct 19 ms 12892 KB Correct.
9 Correct 21 ms 344 KB Correct.
10 Correct 31 ms 344 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 860 KB Correct.
2 Correct 28 ms 1028 KB Correct.
3 Correct 25 ms 968 KB Correct.
4 Correct 23 ms 344 KB Correct.
5 Correct 25 ms 348 KB Correct.
6 Correct 7 ms 5468 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 36956 KB Correct.
2 Correct 937 ms 1092 KB Correct.
3 Correct 779 ms 1136 KB Correct.
4 Correct 851 ms 1076 KB Correct.
5 Correct 700 ms 600 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 1048 KB Correct.
3 Correct 24 ms 1032 KB Correct.
4 Correct 25 ms 6388 KB Correct.
5 Correct 19 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1088 KB Correct.
2 Correct 24 ms 1024 KB Correct.
3 Correct 50 ms 48212 KB Correct.
4 Correct 19 ms 4284 KB Correct.
5 Correct 21 ms 348 KB Correct.
6 Correct 27 ms 1072 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 3948 KB Correct.
2 Correct 89 ms 4064 KB Correct.
3 Correct 2496 ms 43032 KB Correct.
4 Correct 2133 ms 11268 KB Correct.
5 Correct 2053 ms 91828 KB Correct.
6 Correct 679 ms 44716 KB Correct.
7 Correct 2130 ms 11760 KB Correct.
8 Correct 2041 ms 2480 KB Correct.
9 Correct 664 ms 2796 KB Correct.
10 Correct 695 ms 3904 KB Correct.
11 Correct 1932 ms 1772 KB Correct.
12 Correct 715 ms 2672 KB Correct.
13 Correct 699 ms 4020 KB Correct.
14 Correct 1631 ms 14752 KB Correct.
15 Correct 2311 ms 5604 KB Correct.
16 Correct 666 ms 2720 KB Correct.
17 Correct 845 ms 2724 KB Correct.
18 Correct 833 ms 2752 KB Correct.
19 Correct 2553 ms 4128 KB Correct.
20 Correct 47 ms 724 KB Correct.
21 Correct 56 ms 2064 KB Correct.
22 Correct 67 ms 5568 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2721 ms 9040 KB Correct.
2 Correct 308 ms 8848 KB Correct.
3 Incorrect 1171 ms 110080 KB Wrong Answer.
4 Halted 0 ms 0 KB -