oj.uz

Submission #749081

# Submission time Handle Problem Language Result Execution time Memory
749081 2023-05-27T09:52:02 Z onebit1024 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 67660 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define all(c) c.begin(), c.end()
#define endl "\n"
 
const double PI=3.141592653589;
 
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");} 
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
 
 
 
double solve(int n, int m, int k, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    vector<vector<pair<int,int>>>adj(n+1);
 
    for(int i = 0;i<m;++i)adj[x[i]].pb({y[i],c[i]}),adj[y[i]].pb({x[i],c[i]});
    k = min(k,70);
 
    priority_queue<vector<double>,vector<vector<double>>,greater<vector<double>>>pq;
 
    vector<vector<double>>dist(n+1, vector<double>(k+1,1e18));
    dist[0][0] = 0,pq.push({0,0,0});
 
    while(!pq.empty()){
        int u = pq.top()[1], j = pq.top()[2];
        double dd = pq.top()[0];
        pq.pop();
 
        if(dd!=dist[u][j])continue;
 
        if(u==h)continue;
        for(auto &[v,c] : adj[u]){
            double curr_dist = dist[v][j],new_dist = dist[u][j]+c;
            if(arr[v]==1)new_dist = dist[u][j]+c;
            else if(arr[v]==0)new_dist = 0;
            else if(arr[v]==2){
                if(j)new_dist = min(new_dist,(dist[u][j-1]+c)/2);                
                if(j+1 <= k){
                    double curr_dist = dist[v][j+1], new_dist = (dist[u][j]+c)/2;
                    if(new_dist < curr_dist){
                        dist[v][j+1] = new_dist;
                        pq.push({new_dist, (double)v,(double)(j+1)});
                    }
                }
            }
            if(new_dist < curr_dist){
                dist[v][j] = new_dist;
                pq.push({new_dist,(double)v,(double)j});
            }
            
        }
    }
    double res = 1e18;
    for(int i = 0;i<=k;++i)res = min(res, dist[h][i]);
    if(res==1e18)res = -1;
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 440 KB Correct.
2 Correct 30 ms 448 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 724 KB Correct.
2 Correct 40 ms 688 KB Correct.
3 Correct 36 ms 696 KB Correct.
4 Correct 43 ms 672 KB Correct.
5 Correct 39 ms 688 KB Correct.
6 Correct 39 ms 3844 KB Correct.
7 Correct 47 ms 3792 KB Correct.
8 Correct 22 ms 7560 KB Correct.
9 Correct 37 ms 424 KB Correct.
10 Correct 34 ms 420 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 688 KB Correct.
2 Correct 36 ms 596 KB Correct.
3 Correct 31 ms 740 KB Correct.
4 Correct 36 ms 420 KB Correct.
5 Correct 35 ms 340 KB Correct.
6 Correct 8 ms 3284 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 21308 KB Correct.
2 Correct 770 ms 796 KB Correct.
3 Correct 648 ms 860 KB Correct.
4 Correct 691 ms 728 KB Correct.
5 Correct 478 ms 464 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 724 KB Correct.
2 Correct 30 ms 664 KB Correct.
3 Correct 29 ms 644 KB Correct.
4 Correct 31 ms 3768 KB Correct.
5 Correct 28 ms 420 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 688 KB Correct.
2 Correct 27 ms 692 KB Correct.
3 Correct 55 ms 27884 KB Correct.
4 Correct 21 ms 2576 KB Correct.
5 Correct 29 ms 340 KB Correct.
6 Correct 29 ms 696 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 1448 KB Correct.
2 Correct 46 ms 1940 KB Correct.
3 Correct 2647 ms 28612 KB Correct.
4 Correct 1844 ms 7112 KB Correct.
5 Correct 2103 ms 62192 KB Correct.
6 Correct 826 ms 33664 KB Correct.
7 Correct 1748 ms 7348 KB Correct.
8 Correct 1549 ms 1612 KB Correct.
9 Correct 363 ms 1436 KB Correct.
10 Correct 405 ms 1936 KB Correct.
11 Correct 1608 ms 1236 KB Correct.
12 Correct 421 ms 1392 KB Correct.
13 Correct 441 ms 1440 KB Correct.
14 Correct 1798 ms 9404 KB Correct.
15 Correct 2266 ms 3040 KB Correct.
16 Correct 407 ms 1460 KB Correct.
17 Correct 469 ms 1420 KB Correct.
18 Correct 499 ms 1460 KB Correct.
19 Correct 1493 ms 2236 KB Correct.
20 Correct 31 ms 588 KB Correct.
21 Correct 33 ms 1084 KB Correct.
22 Correct 39 ms 3876 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1238 ms 3804 KB Correct.
2 Correct 123 ms 3920 KB Correct.
3 Correct 994 ms 67660 KB Correct.
4 Execution timed out 3069 ms 5544 KB Time limit exceeded
5 Halted 0 ms 0 KB -