oj.uz

Submission #749072

# Submission time Handle Problem Language Result Execution time Memory
749072 2023-05-27T09:47:26 Z onebit1024 Cyberland (APIO23_cyberland) C++17
97 / 100
 2620 ms 87196 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,60);
 
    priority_queue<vector<double>,vector<vector<double>>,greater<vector<double>>>pq;
 
    vector<vector<double>>dist(n+1, vector<double>(k+1,1e18));
    for(int j = 0;j<=k;++j)dist[0][j] = 0,pq.push({0,0,(double)j});
 
    vector<vector<int>>visited(n+1, vector<int>(k+1));
    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 91 ms 368 KB Correct.
2 Correct 108 ms 348 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 1204 KB Correct.
2 Correct 423 ms 1240 KB Correct.
3 Correct 387 ms 1228 KB Correct.
4 Correct 408 ms 1276 KB Correct.
5 Correct 426 ms 1204 KB Correct.
6 Correct 494 ms 8308 KB Correct.
7 Correct 621 ms 8240 KB Correct.
8 Correct 252 ms 15724 KB Correct.
9 Correct 326 ms 492 KB Correct.
10 Correct 325 ms 500 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 1112 KB Correct.
2 Correct 467 ms 1260 KB Correct.
3 Correct 444 ms 1296 KB Correct.
4 Correct 387 ms 440 KB Correct.
5 Correct 386 ms 600 KB Correct.
6 Correct 101 ms 6068 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 30884 KB Correct.
2 Correct 846 ms 884 KB Correct.
3 Correct 651 ms 912 KB Correct.
4 Correct 749 ms 892 KB Correct.
5 Correct 555 ms 616 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 1204 KB Correct.
2 Correct 233 ms 1232 KB Correct.
3 Correct 296 ms 1124 KB Correct.
4 Correct 299 ms 8104 KB Correct.
5 Correct 173 ms 496 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 1344 KB Correct.
2 Correct 219 ms 1308 KB Correct.
3 Correct 68 ms 40360 KB Correct.
4 Correct 187 ms 8288 KB Correct.
5 Correct 263 ms 512 KB Correct.
6 Correct 271 ms 1384 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 1512 KB Correct.
2 Correct 48 ms 2084 KB Correct.
3 Correct 2620 ms 38176 KB Correct.
4 Correct 2017 ms 9612 KB Correct.
5 Correct 1835 ms 67992 KB Correct.
6 Correct 811 ms 35188 KB Correct.
7 Correct 1913 ms 10104 KB Correct.
8 Correct 1721 ms 2136 KB Correct.
9 Correct 485 ms 1572 KB Correct.
10 Correct 405 ms 1912 KB Correct.
11 Correct 1609 ms 1220 KB Correct.
12 Correct 435 ms 1524 KB Correct.
13 Correct 426 ms 1520 KB Correct.
14 Correct 1651 ms 12452 KB Correct.
15 Correct 2056 ms 4032 KB Correct.
16 Correct 352 ms 1500 KB Correct.
17 Correct 464 ms 1668 KB Correct.
18 Correct 463 ms 1704 KB Correct.
19 Correct 1431 ms 2404 KB Correct.
20 Correct 30 ms 556 KB Correct.
21 Correct 35 ms 1200 KB Correct.
22 Correct 38 ms 4024 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 3896 KB Correct.
2 Correct 107 ms 3684 KB Correct.
3 Incorrect 1241 ms 87196 KB Wrong Answer.
4 Halted 0 ms 0 KB -