oj.uz

Submission #1081406

# Submission time Handle Problem Language Result Execution time Memory
1081406 2024-08-30T04:13:04 Z Muhammet Cyberland (APIO23_cyberland) C++17
97 / 100
 2838 ms 96920 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,50);

    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 24 ms 860 KB Correct.
2 Correct 25 ms 860 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1880 KB Correct.
2 Correct 27 ms 2108 KB Correct.
3 Correct 27 ms 2140 KB Correct.
4 Correct 26 ms 2100 KB Correct.
5 Correct 27 ms 2060 KB Correct.
6 Correct 26 ms 7348 KB Correct.
7 Correct 36 ms 7500 KB Correct.
8 Correct 16 ms 13404 KB Correct.
9 Correct 23 ms 1368 KB Correct.
10 Correct 22 ms 1452 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1880 KB Correct.
2 Correct 29 ms 1916 KB Correct.
3 Correct 26 ms 1896 KB Correct.
4 Correct 23 ms 1372 KB Correct.
5 Correct 25 ms 1372 KB Correct.
6 Correct 9 ms 5724 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 38352 KB Correct.
2 Correct 916 ms 2056 KB Correct.
3 Correct 789 ms 2076 KB Correct.
4 Correct 851 ms 2000 KB Correct.
5 Correct 686 ms 1520 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2208 KB Correct.
2 Correct 26 ms 2056 KB Correct.
3 Correct 35 ms 2028 KB Correct.
4 Correct 26 ms 6916 KB Correct.
5 Correct 38 ms 1316 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2076 KB Correct.
2 Correct 25 ms 1936 KB Correct.
3 Correct 48 ms 50260 KB Correct.
4 Correct 35 ms 4836 KB Correct.
5 Correct 23 ms 1368 KB Correct.
6 Correct 27 ms 2000 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 815 ms 4864 KB Correct.
2 Correct 97 ms 4212 KB Correct.
3 Correct 2838 ms 45488 KB Correct.
4 Correct 2378 ms 13640 KB Correct.
5 Correct 2442 ms 93648 KB Correct.
6 Correct 846 ms 47124 KB Correct.
7 Correct 2275 ms 12868 KB Correct.
8 Correct 2204 ms 4068 KB Correct.
9 Correct 667 ms 3860 KB Correct.
10 Correct 731 ms 4792 KB Correct.
11 Correct 2036 ms 3164 KB Correct.
12 Correct 772 ms 3628 KB Correct.
13 Correct 821 ms 5060 KB Correct.
14 Correct 1758 ms 16496 KB Correct.
15 Correct 2357 ms 7652 KB Correct.
16 Correct 674 ms 3836 KB Correct.
17 Correct 899 ms 3672 KB Correct.
18 Correct 855 ms 3732 KB Correct.
19 Correct 2539 ms 5912 KB Correct.
20 Correct 49 ms 728 KB Correct.
21 Correct 54 ms 2068 KB Correct.
22 Correct 65 ms 6344 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1943 ms 8748 KB Correct.
2 Correct 217 ms 8504 KB Correct.
3 Incorrect 997 ms 96920 KB Wrong Answer.
4 Halted 0 ms 0 KB -