oj.uz

Submission #752485

# Submission time Handle Problem Language Result Execution time Memory
752485 2023-06-03T04:58:31 Z bachhoangxuan Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 288804 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;
        }
        if(d!=dist[u][k]) 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 23 ms 412 KB Correct.
2 Correct 21 ms 408 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 680 KB Correct.
2 Correct 31 ms 672 KB Correct.
3 Correct 28 ms 724 KB Correct.
4 Correct 31 ms 596 KB Correct.
5 Correct 37 ms 672 KB Correct.
6 Correct 28 ms 3884 KB Correct.
7 Correct 44 ms 3808 KB Correct.
8 Correct 17 ms 7512 KB Correct.
9 Correct 30 ms 428 KB Correct.
10 Correct 31 ms 416 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 692 KB Correct.
2 Correct 35 ms 688 KB Correct.
3 Correct 33 ms 716 KB Correct.
4 Correct 34 ms 428 KB Correct.
5 Correct 33 ms 340 KB Correct.
6 Correct 7 ms 3284 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 21308 KB Correct.
2 Correct 582 ms 716 KB Correct.
3 Correct 484 ms 748 KB Correct.
4 Correct 512 ms 652 KB Correct.
5 Correct 386 ms 580 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 676 KB Correct.
2 Correct 31 ms 632 KB Correct.
3 Correct 27 ms 724 KB Correct.
4 Correct 26 ms 3668 KB Correct.
5 Correct 27 ms 424 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 700 KB Correct.
2 Correct 25 ms 676 KB Correct.
3 Correct 58 ms 27888 KB Correct.
4 Correct 19 ms 2564 KB Correct.
5 Correct 28 ms 412 KB Correct.
6 Correct 27 ms 704 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 2360 KB Correct.
2 Correct 82 ms 3636 KB Correct.
3 Correct 1540 ms 27296 KB Correct.
4 Correct 1312 ms 7024 KB Correct.
5 Correct 2287 ms 81152 KB Correct.
6 Correct 1085 ms 40176 KB Correct.
7 Correct 1266 ms 7084 KB Correct.
8 Correct 1111 ms 1616 KB Correct.
9 Correct 505 ms 2164 KB Correct.
10 Correct 478 ms 2428 KB Correct.
11 Correct 1130 ms 1008 KB Correct.
12 Correct 491 ms 2332 KB Correct.
13 Correct 515 ms 2492 KB Correct.
14 Correct 1076 ms 8988 KB Correct.
15 Correct 1334 ms 2868 KB Correct.
16 Correct 486 ms 2176 KB Correct.
17 Correct 616 ms 2196 KB Correct.
18 Correct 571 ms 1632 KB Correct.
19 Correct 1548 ms 2316 KB Correct.
20 Correct 32 ms 600 KB Correct.
21 Correct 37 ms 1260 KB Correct.
22 Correct 89 ms 5188 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1828 ms 7684 KB Correct.
2 Correct 285 ms 13928 KB Correct.
3 Correct 669 ms 66136 KB Correct.
4 Correct 2901 ms 3980 KB Correct.
5 Execution timed out 3070 ms 288804 KB Time limit exceeded
6 Halted 0 ms 0 KB -