oj.uz

Submission #752482

# Submission time Handle Problem Language Result Execution time Memory
752482 2023-06-03T04:56:33 Z bachhoangxuan Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 288956 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,67);
    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 21 ms 364 KB Correct.
2 Correct 21 ms 448 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 696 KB Correct.
2 Correct 30 ms 724 KB Correct.
3 Correct 32 ms 684 KB Correct.
4 Correct 30 ms 696 KB Correct.
5 Correct 32 ms 692 KB Correct.
6 Correct 30 ms 3864 KB Correct.
7 Correct 35 ms 3864 KB Correct.
8 Correct 17 ms 7472 KB Correct.
9 Correct 30 ms 340 KB Correct.
10 Correct 31 ms 340 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 684 KB Correct.
2 Correct 34 ms 660 KB Correct.
3 Correct 36 ms 708 KB Correct.
4 Correct 33 ms 420 KB Correct.
5 Correct 33 ms 408 KB Correct.
6 Correct 7 ms 3284 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 21300 KB Correct.
2 Correct 574 ms 716 KB Correct.
3 Correct 505 ms 804 KB Correct.
4 Correct 537 ms 784 KB Correct.
5 Correct 408 ms 460 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 716 KB Correct.
2 Correct 40 ms 660 KB Correct.
3 Correct 31 ms 696 KB Correct.
4 Correct 33 ms 3668 KB Correct.
5 Correct 25 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 668 KB Correct.
2 Correct 28 ms 668 KB Correct.
3 Correct 55 ms 27972 KB Correct.
4 Correct 19 ms 2480 KB Correct.
5 Correct 30 ms 412 KB Correct.
6 Correct 29 ms 596 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 2356 KB Correct.
2 Correct 89 ms 3632 KB Correct.
3 Correct 1568 ms 27364 KB Correct.
4 Correct 1250 ms 7132 KB Correct.
5 Correct 2547 ms 81236 KB Correct.
6 Correct 1281 ms 40148 KB Correct.
7 Correct 1231 ms 6988 KB Correct.
8 Correct 1132 ms 1712 KB Correct.
9 Correct 524 ms 2276 KB Correct.
10 Correct 524 ms 2316 KB Correct.
11 Correct 1083 ms 964 KB Correct.
12 Correct 525 ms 2284 KB Correct.
13 Correct 554 ms 2448 KB Correct.
14 Correct 1074 ms 9068 KB Correct.
15 Correct 1388 ms 2872 KB Correct.
16 Correct 522 ms 2276 KB Correct.
17 Correct 658 ms 2160 KB Correct.
18 Correct 647 ms 1604 KB Correct.
19 Correct 1628 ms 2176 KB Correct.
20 Correct 36 ms 528 KB Correct.
21 Correct 43 ms 1212 KB Correct.
22 Correct 113 ms 5252 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1980 ms 7708 KB Correct.
2 Correct 311 ms 13936 KB Correct.
3 Correct 648 ms 66096 KB Correct.
4 Correct 2933 ms 3944 KB Correct.
5 Execution timed out 3064 ms 288956 KB Time limit exceeded
6 Halted 0 ms 0 KB -