oj.uz

Submission #749070

# Submission time Handle Problem Language Result Execution time Memory
749070 2023-05-27T09:46:11 Z onebit1024 Cyberland (APIO23_cyberland) C++17
97 / 100
 2826 ms 2097152 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]});

    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 93 ms 388 KB Correct.
2 Correct 100 ms 464 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 1288 KB Correct.
2 Correct 422 ms 1212 KB Correct.
3 Correct 429 ms 1220 KB Correct.
4 Correct 398 ms 1248 KB Correct.
5 Correct 524 ms 1216 KB Correct.
6 Correct 457 ms 8236 KB Correct.
7 Correct 545 ms 8236 KB Correct.
8 Correct 268 ms 15792 KB Correct.
9 Correct 325 ms 512 KB Correct.
10 Correct 317 ms 612 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 1068 KB Correct.
2 Correct 469 ms 1160 KB Correct.
3 Correct 478 ms 1272 KB Correct.
4 Correct 431 ms 512 KB Correct.
5 Correct 431 ms 508 KB Correct.
6 Correct 108 ms 6112 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 30880 KB Correct.
2 Correct 777 ms 880 KB Correct.
3 Correct 618 ms 828 KB Correct.
4 Correct 727 ms 876 KB Correct.
5 Correct 476 ms 624 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 1160 KB Correct.
2 Correct 226 ms 1152 KB Correct.
3 Correct 265 ms 1192 KB Correct.
4 Correct 320 ms 8184 KB Correct.
5 Correct 185 ms 500 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 1336 KB Correct.
2 Correct 232 ms 1212 KB Correct.
3 Correct 79 ms 40396 KB Correct.
4 Correct 212 ms 8292 KB Correct.
5 Correct 337 ms 460 KB Correct.
6 Correct 252 ms 1348 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 1584 KB Correct.
2 Correct 49 ms 2084 KB Correct.
3 Correct 2826 ms 38180 KB Correct.
4 Correct 1937 ms 9636 KB Correct.
5 Correct 1863 ms 67996 KB Correct.
6 Correct 734 ms 35276 KB Correct.
7 Correct 1876 ms 10044 KB Correct.
8 Correct 1565 ms 2192 KB Correct.
9 Correct 368 ms 1512 KB Correct.
10 Correct 406 ms 1948 KB Correct.
11 Correct 1474 ms 1224 KB Correct.
12 Correct 415 ms 1568 KB Correct.
13 Correct 391 ms 1584 KB Correct.
14 Correct 1561 ms 12696 KB Correct.
15 Correct 2053 ms 4044 KB Correct.
16 Correct 351 ms 1672 KB Correct.
17 Correct 460 ms 1652 KB Correct.
18 Correct 450 ms 1552 KB Correct.
19 Correct 1410 ms 2280 KB Correct.
20 Correct 26 ms 468 KB Correct.
21 Correct 41 ms 1176 KB Correct.
22 Correct 42 ms 3968 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 842 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -