oj.uz

Submission #749075

# Submission time Handle Problem Language Result Execution time Memory
749075 2023-05-27T09:48:43 Z onebit1024 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 110688 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,80);
 
    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 102 ms 408 KB Correct.
2 Correct 96 ms 396 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 1200 KB Correct.
2 Correct 427 ms 1236 KB Correct.
3 Correct 394 ms 1220 KB Correct.
4 Correct 462 ms 1284 KB Correct.
5 Correct 418 ms 1260 KB Correct.
6 Correct 484 ms 8136 KB Correct.
7 Correct 641 ms 8196 KB Correct.
8 Correct 263 ms 15748 KB Correct.
9 Correct 342 ms 496 KB Correct.
10 Correct 323 ms 544 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 1100 KB Correct.
2 Correct 464 ms 1132 KB Correct.
3 Correct 410 ms 1192 KB Correct.
4 Correct 383 ms 552 KB Correct.
5 Correct 391 ms 468 KB Correct.
6 Correct 93 ms 6092 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 30888 KB Correct.
2 Correct 775 ms 884 KB Correct.
3 Correct 633 ms 996 KB Correct.
4 Correct 683 ms 888 KB Correct.
5 Correct 452 ms 596 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 1168 KB Correct.
2 Correct 211 ms 1140 KB Correct.
3 Correct 235 ms 1264 KB Correct.
4 Correct 272 ms 8168 KB Correct.
5 Correct 172 ms 468 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 1380 KB Correct.
2 Correct 215 ms 1208 KB Correct.
3 Correct 66 ms 40312 KB Correct.
4 Correct 206 ms 8384 KB Correct.
5 Correct 249 ms 468 KB Correct.
6 Correct 239 ms 1308 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 1640 KB Correct.
2 Correct 50 ms 2084 KB Correct.
3 Correct 2788 ms 38320 KB Correct.
4 Correct 1949 ms 9624 KB Correct.
5 Correct 1884 ms 67992 KB Correct.
6 Correct 1087 ms 35228 KB Correct.
7 Correct 2178 ms 10132 KB Correct.
8 Correct 1906 ms 2132 KB Correct.
9 Correct 419 ms 1600 KB Correct.
10 Correct 444 ms 1920 KB Correct.
11 Correct 1689 ms 1264 KB Correct.
12 Correct 434 ms 1520 KB Correct.
13 Correct 448 ms 1544 KB Correct.
14 Correct 1713 ms 12576 KB Correct.
15 Correct 2636 ms 4004 KB Correct.
16 Correct 374 ms 1504 KB Correct.
17 Correct 499 ms 1532 KB Correct.
18 Correct 481 ms 1556 KB Correct.
19 Correct 1466 ms 2264 KB Correct.
20 Correct 27 ms 468 KB Correct.
21 Correct 36 ms 1188 KB Correct.
22 Correct 36 ms 4004 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1452 ms 4096 KB Correct.
2 Correct 133 ms 4212 KB Correct.
3 Correct 1752 ms 110688 KB Correct.
4 Execution timed out 3068 ms 7384 KB Time limit exceeded
5 Halted 0 ms 0 KB -