oj.uz

Submission #752491

# Submission time Handle Problem Language Result Execution time Memory
752491 2023-06-03T05:19:49 Z bachhoangxuan Cyberland (APIO23_cyberland) C++17
100 / 100
 1837 ms 66456 KB 
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pdi pair<double,int>
#define fi first
#define se second
const double inf=1e18;
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,inf));
    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]});
    }
    vector<int> vis(N,0);
    dist[0][0]=0;vis[0]=1;
    queue<int> q;q.push(0);
    while(!q.empty()){
        int u=q.front();q.pop();
        if(arr[u]==0) dist[u][0]=0;
        if(u==T) continue;
        for(auto [v,w]:edge[u]){
            if(vis[v]) continue;
            vis[v]=1;q.push(v);
        }
    }
    bool ok=false;
    double res=1e14;
    for(int k=0;k<=K;k++){
        priority_queue<pdi,vector<pdi>,greater<pdi>> pq;
        for(int i=0;i<N;i++){
            if(i!=T && dist[i][k]!=inf) pq.push({dist[i][k],i});
        }
        while(!pq.empty()){
            auto [d,u]=pq.top();pq.pop();
            if(u==T) continue;
            if(d!=dist[u][k]) continue;
            for(auto [v,w]:edge[u]){
                if(arr[u]==2 && k!=K) dist[v][k+1]=min(dist[v][k+1],dist[u][k]/2+w);
                if(dist[u][k]+w<dist[v][k]){
                    dist[v][k]=dist[u][k]+w;
                    pq.push({dist[u][k]+w,v});
                }
            }
        }
        if(dist[T][k]!=inf) ok=true;
        res=min(res,dist[T][k]);
    }
    if(ok) return res;
    else return -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 468 KB Correct.
2 Correct 25 ms 456 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 684 KB Correct.
2 Correct 33 ms 724 KB Correct.
3 Correct 33 ms 680 KB Correct.
4 Correct 33 ms 596 KB Correct.
5 Correct 31 ms 744 KB Correct.
6 Correct 30 ms 3964 KB Correct.
7 Correct 36 ms 3864 KB Correct.
8 Correct 19 ms 7644 KB Correct.
9 Correct 32 ms 432 KB Correct.
10 Correct 32 ms 416 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 696 KB Correct.
2 Correct 36 ms 712 KB Correct.
3 Correct 42 ms 724 KB Correct.
4 Correct 34 ms 416 KB Correct.
5 Correct 36 ms 428 KB Correct.
6 Correct 8 ms 3400 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 21816 KB Correct.
2 Correct 120 ms 688 KB Correct.
3 Correct 98 ms 744 KB Correct.
4 Correct 107 ms 712 KB Correct.
5 Correct 72 ms 412 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 616 KB Correct.
2 Correct 31 ms 724 KB Correct.
3 Correct 31 ms 704 KB Correct.
4 Correct 29 ms 3668 KB Correct.
5 Correct 30 ms 412 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 696 KB Correct.
2 Correct 26 ms 724 KB Correct.
3 Correct 64 ms 28152 KB Correct.
4 Correct 20 ms 2584 KB Correct.
5 Correct 30 ms 420 KB Correct.
6 Correct 31 ms 696 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 596 KB Correct.
2 Correct 17 ms 852 KB Correct.
3 Correct 738 ms 26660 KB Correct.
4 Correct 316 ms 6828 KB Correct.
5 Correct 674 ms 16688 KB Correct.
6 Correct 183 ms 7824 KB Correct.
7 Correct 294 ms 6784 KB Correct.
8 Correct 226 ms 1704 KB Correct.
9 Correct 102 ms 704 KB Correct.
10 Correct 102 ms 676 KB Correct.
11 Correct 214 ms 736 KB Correct.
12 Correct 118 ms 660 KB Correct.
13 Correct 117 ms 644 KB Correct.
14 Correct 350 ms 8988 KB Correct.
15 Correct 253 ms 2572 KB Correct.
16 Correct 113 ms 616 KB Correct.
17 Correct 128 ms 736 KB Correct.
18 Correct 125 ms 708 KB Correct.
19 Correct 354 ms 688 KB Correct.
20 Correct 7 ms 340 KB Correct.
21 Correct 12 ms 608 KB Correct.
22 Correct 11 ms 980 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 1004 KB Correct.
2 Correct 37 ms 1364 KB Correct.
3 Correct 725 ms 66456 KB Correct.
4 Correct 311 ms 2892 KB Correct.
5 Correct 1462 ms 27568 KB Correct.
6 Correct 401 ms 10940 KB Correct.
7 Correct 590 ms 12720 KB Correct.
8 Correct 257 ms 1488 KB Correct.
9 Correct 196 ms 992 KB Correct.
10 Correct 201 ms 1068 KB Correct.
11 Correct 210 ms 576 KB Correct.
12 Correct 209 ms 1040 KB Correct.
13 Correct 200 ms 1000 KB Correct.
14 Correct 1837 ms 27448 KB Correct.
15 Correct 1359 ms 33212 KB Correct.
16 Correct 486 ms 11904 KB Correct.
17 Correct 286 ms 2796 KB Correct.
18 Correct 196 ms 972 KB Correct.
19 Correct 232 ms 992 KB Correct.
20 Correct 219 ms 972 KB Correct.
21 Correct 687 ms 980 KB Correct.
22 Correct 17 ms 340 KB Correct.
23 Correct 16 ms 872 KB Correct.
24 Correct 22 ms 1296 KB Correct.