oj.uz

Submission #750010

# Submission time Handle Problem Language Result Execution time Memory
750010 2023-05-29T03:44:17 Z Cookie Cyberland (APIO23_cyberland) C++17
100 / 100
 1996 ms 128952 KB 
#include<bits/stdc++.h>
#include "cyberland.h"
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 1e5;
const ll prec = 1e-6;
struct ch{
    int u, take; ld dd;
};
struct cmp{
    bool operator()(const ch &a, const ch &b){
        return(a.dd > b.dd);
    }
};
vt<pii>adj[mxn + 1];
ld d[mxn + 1][71];
bool vis[mxn + 1], go[mxn + 1][71];
void dfs(int s){
    vis[s] = 1;
    for(auto [v, w]: adj[s]){
        if(!vis[v])dfs(v);
    }
}
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) {
    k = min(k, 70);
    forr(i, 0, n){
        adj[i].clear();
        forr(j, 0, k + 1){
            d[i][j] = 1e18; go[i][j] = 0;
        }
        vis[i] = 0;
    }
    forr(i, 0, m){
        int u = x[i], v = y[i], w = c[i];
        adj[u].pb({v, w}); adj[v].pb({u, w});
    }
    dfs(0);
    if(!vis[h])return(-1);
    
    d[0][0] = 0;
    for(int tt = 0; tt <= k; tt++){
        priority_queue<ch, vt<ch>, cmp>pq; 
        for(int i = 0; i < n; i++){
            if(d[i][tt] != 1e18)pq.push({i, tt, d[i][tt]});
        }
    while(!pq.empty()){
        auto [u, take, dd] = pq.top(); pq.pop();
        if((abs(dd - d[u][take]) > prec) || u == h)continue;
        for(auto [v, w]: adj[u]){
            if(arr[v] == 0 && d[v][tt] != 0){
                d[v][tt] = 0;
                pq.push({v, tt, d[v][tt]});
                continue;
            }
            if(d[v][take] > d[u][take] + w){
                d[v][take] = d[u][take] + w;
                pq.push({v, take, d[v][take]});
            }
            if(arr[u] == 2 && take < k){
                d[v][take + 1] = min(d[v][take + 1], (d[u][take] / 2.0) + w);
            }
        }
    }
    }
    ld ans = 1e18;
    for(int i = 0; i <= k; i++)ans = min(ans, d[h][i]);
    return(ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2944 KB Correct.
2 Correct 29 ms 2744 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3956 KB Correct.
2 Correct 40 ms 3916 KB Correct.
3 Correct 39 ms 3960 KB Correct.
4 Correct 40 ms 4056 KB Correct.
5 Correct 40 ms 3988 KB Correct.
6 Correct 45 ms 14980 KB Correct.
7 Correct 55 ms 14804 KB Correct.
8 Correct 32 ms 27272 KB Correct.
9 Correct 39 ms 2772 KB Correct.
10 Correct 36 ms 2848 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3924 KB Correct.
2 Correct 41 ms 3924 KB Correct.
3 Correct 39 ms 3924 KB Correct.
4 Correct 40 ms 2900 KB Correct.
5 Correct 38 ms 2852 KB Correct.
6 Correct 15 ms 12780 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 76676 KB Correct.
2 Correct 196 ms 4044 KB Correct.
3 Correct 170 ms 4040 KB Correct.
4 Correct 190 ms 3988 KB Correct.
5 Correct 125 ms 2836 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4044 KB Correct.
2 Correct 36 ms 4052 KB Correct.
3 Correct 36 ms 4004 KB Correct.
4 Correct 41 ms 15020 KB Correct.
5 Correct 31 ms 2772 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4000 KB Correct.
2 Correct 31 ms 3980 KB Correct.
3 Correct 93 ms 97236 KB Correct.
4 Correct 29 ms 11604 KB Correct.
5 Correct 35 ms 2772 KB Correct.
6 Correct 33 ms 4036 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 4136 KB Correct.
2 Correct 30 ms 4948 KB Correct.
3 Correct 863 ms 122076 KB Correct.
4 Correct 416 ms 29704 KB Correct.
5 Correct 937 ms 53124 KB Correct.
6 Correct 309 ms 19896 KB Correct.
7 Correct 432 ms 32416 KB Correct.
8 Correct 308 ms 7136 KB Correct.
9 Correct 150 ms 4024 KB Correct.
10 Correct 138 ms 3984 KB Correct.
11 Correct 293 ms 4316 KB Correct.
12 Correct 172 ms 4044 KB Correct.
13 Correct 165 ms 4108 KB Correct.
14 Correct 436 ms 61024 KB Correct.
15 Correct 346 ms 18376 KB Correct.
16 Correct 156 ms 4000 KB Correct.
17 Correct 186 ms 3992 KB Correct.
18 Correct 164 ms 4032 KB Correct.
19 Correct 446 ms 4252 KB Correct.
20 Correct 11 ms 2772 KB Correct.
21 Correct 15 ms 3844 KB Correct.
22 Correct 23 ms 4308 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 3980 KB Correct.
2 Correct 56 ms 4820 KB Correct.
3 Correct 894 ms 128952 KB Correct.
4 Correct 430 ms 10776 KB Correct.
5 Correct 1996 ms 53172 KB Correct.
6 Correct 607 ms 20064 KB Correct.
7 Correct 762 ms 47948 KB Correct.
8 Correct 428 ms 4596 KB Correct.
9 Correct 299 ms 4048 KB Correct.
10 Correct 266 ms 3972 KB Correct.
11 Correct 303 ms 2936 KB Correct.
12 Correct 350 ms 3984 KB Correct.
13 Correct 349 ms 4044 KB Correct.
14 Correct 1922 ms 53204 KB Correct.
15 Correct 1636 ms 64572 KB Correct.
16 Correct 653 ms 25016 KB Correct.
17 Correct 439 ms 7244 KB Correct.
18 Correct 312 ms 3980 KB Correct.
19 Correct 399 ms 4012 KB Correct.
20 Correct 332 ms 4172 KB Correct.
21 Correct 936 ms 3992 KB Correct.
22 Correct 20 ms 2772 KB Correct.
23 Correct 25 ms 3924 KB Correct.
24 Correct 39 ms 4180 KB Correct.