oj.uz

Submission #752481

# Submission time Handle Problem Language Result Execution time Memory
752481 2023-06-03T04:53:04 Z bachhoangxuan Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 91224 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pdi pair<double,pii>
#define fi first
#define se second

double solve(int N, int M, int K, int T, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    K=min(K,100);
    vector<vector<double>> dist(N,vector<double>(K+1,1e14));
    vector<vector<pii>> edge(N);
    for(int i=0;i<M;i++){
        edge[x[i]].push_back({y[i],c[i]});
        edge[y[i]].push_back({x[i],c[i]});
    }
    priority_queue<pdi,vector<pdi>,greater<pdi>> pq;
    dist[0][0]=0;pq.push({0,{0,0}});
    bool ok=false;
    double res=1e14;
    while(!pq.empty()){
        auto [d,x]=pq.top();pq.pop();
        int u=x.fi,k=x.se;
        if(u==T){
            res=min(res,d);
            ok=true;continue;
        }
        for(auto [v,w]:edge[u]){
            double nd=dist[u][k]*(arr[u]?1.0/arr[u]:0)+w;
            int nk=k+(arr[u]==2);
            if(nk<=K && dist[v][nk]>nd){
                dist[v][nk]=nd;
                pq.push({nd,{v,nk}});
            }
            if(dist[u][k]+w<dist[v][k]){
                dist[v][k]=dist[u][k]+w;
                pq.push({dist[u][k]+w,{v,k}});
            }
        }
    }
    if(ok) return res;
    else return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 476 KB Correct.
2 Correct 24 ms 384 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 676 KB Correct.
2 Correct 29 ms 680 KB Correct.
3 Correct 38 ms 636 KB Correct.
4 Correct 29 ms 700 KB Correct.
5 Correct 30 ms 688 KB Correct.
6 Correct 29 ms 3856 KB Correct.
7 Correct 42 ms 3864 KB Correct.
8 Correct 25 ms 7544 KB Correct.
9 Correct 28 ms 340 KB Correct.
10 Correct 28 ms 420 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 688 KB Correct.
2 Correct 32 ms 664 KB Correct.
3 Correct 31 ms 720 KB Correct.
4 Correct 36 ms 416 KB Correct.
5 Correct 33 ms 408 KB Correct.
6 Correct 11 ms 3284 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 21308 KB Correct.
2 Correct 631 ms 824 KB Correct.
3 Correct 513 ms 748 KB Correct.
4 Correct 570 ms 812 KB Correct.
5 Correct 429 ms 556 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 712 KB Correct.
2 Correct 30 ms 684 KB Correct.
3 Correct 31 ms 684 KB Correct.
4 Correct 28 ms 3668 KB Correct.
5 Correct 25 ms 404 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 724 KB Correct.
2 Correct 29 ms 680 KB Correct.
3 Correct 54 ms 27892 KB Correct.
4 Correct 21 ms 2484 KB Correct.
5 Correct 40 ms 388 KB Correct.
6 Correct 29 ms 696 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 2304 KB Correct.
2 Correct 106 ms 3748 KB Correct.
3 Correct 1577 ms 27204 KB Correct.
4 Correct 1289 ms 6920 KB Correct.
5 Correct 2487 ms 81352 KB Correct.
6 Correct 1217 ms 40216 KB Correct.
7 Correct 1301 ms 6996 KB Correct.
8 Correct 1171 ms 1656 KB Correct.
9 Correct 566 ms 2188 KB Correct.
10 Correct 539 ms 2252 KB Correct.
11 Correct 1121 ms 1024 KB Correct.
12 Correct 542 ms 2272 KB Correct.
13 Correct 560 ms 2600 KB Correct.
14 Correct 1121 ms 9084 KB Correct.
15 Correct 1359 ms 3080 KB Correct.
16 Correct 518 ms 2156 KB Correct.
17 Correct 644 ms 2140 KB Correct.
18 Correct 636 ms 1652 KB Correct.
19 Correct 1571 ms 2300 KB Correct.
20 Correct 34 ms 560 KB Correct.
21 Correct 39 ms 1220 KB Correct.
22 Correct 113 ms 5188 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2889 ms 9048 KB Correct.
2 Correct 439 ms 16660 KB Correct.
3 Correct 1059 ms 91224 KB Correct.
4 Execution timed out 3064 ms 6388 KB Time limit exceeded
5 Halted 0 ms 0 KB -