oj.uz

Submission #1095133

# Submission time Handle Problem Language Result Execution time Memory
1095133 2024-10-01T11:07:35 Z RiverFlow Cyberland (APIO23_cyberland) C++17
97 / 100
 662 ms 64540 KB 
#include "cyberland.h"
 
#include <bits/stdc++.h>
 
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
 
using namespace std;
 
template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b or a == -1) { a = b; return 1; } return 0;
}
 
const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;
 
 
struct edge {
    int u, v, w;
    edge () {};
    edge (int _u, int _v, int _w) {
        u = _u, v = _v, w = _w;
    }
} e[N];
 
int n, m, k, h, ar[N];
vec<pair<int, int>> g[N];
 
#define ld double
const ld esp = (ld)1e-9;
namespace SUB1 {
const int K = 64;
ld dis[N][K];
ld sol() {
    FOR(i, 0, n - 1)
    FOR(j, 0, k) dis[i][j] = -1;
    dis[0][0] = 0;
    #define T pair<ld, ii>
    priority_queue<T, vec<T>, greater<T>> pq;
    pq.push(_mp(0, _mp(0, 0)));
    while (!pq.empty()) {
        auto x = pq.top(); pq.pop();
        int u = x.se.fi;
        int t = x.se.se;
//        cout<<u<<' '<<t<<' '<<dis[u][t]<<nl;
        if (u == h) continue ;
        if (abs(x.fi - dis[u][t]) > esp) continue ;
        for(auto j : g[u]) {
            int v = j.fi;
            // khong dung
            if (ar[v] == 0) {
                if (dis[v][0]==-1){
                    dis[v][0]=0;
                    pq.push(_mp(0, _mp(v,0)));
                }
            }else if(ar[v]==1){
                if (mini(dis[v][t], dis[u][t] + j.se)){
                    pq.push(_mp(dis[v][t], _mp(v, t)));
                }
            }else{
                if (mini(dis[v][t], dis[u][t] + j.se)){
                    pq.push(_mp(dis[v][t], _mp(v, t)));
                }
                //arr[v]=2 ->
                if (t + 1 <= k and mini(dis[v][t+1], (dis[u][t] + j.se)/2.0)){
                    pq.push(_mp(dis[v][t+1], _mp(v, t+1)));
                }
            }
        }
    }
    ld ans=-1;
    FOR(i,0,k){
        if (dis[h][i]!=-1){
//            cout << h << ' ' << i << ' ' << dis[h][i] << nl;
            mini(ans, dis[h][i]);
        }
    }
//    cout << fixed << setprecision(6) << "ans: " << ans << nl;
    return ans;
}
};
 
ld solve(int N, int M, int K, int H,
    vector<int> x, vector<int> y,
    vector<int> c, vector<int> arr) {
 
  	K = min(K, 63);
  
    n = N, m = M, k = K, h = H;
 
    FOR(i, 0, n - 1) ar[i] = arr[i];
 
    FOR(i, 0, n - 1) g[i].clear();
 
    for(int i = 0; i < m; ++i) {
        e[i] = edge(x[i], y[i], c[i]);
        g[x[i]].emplace_back(y[i], c[i]);
        g[y[i]].emplace_back(x[i], c[i]);
    }
 
        return SUB1::sol();
    
 
    return 0;
}
 
 
/*     Let the river flows naturally     */

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5468 KB Correct.
2 Correct 15 ms 5464 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6492 KB Correct.
2 Correct 20 ms 6428 KB Correct.
3 Correct 19 ms 6492 KB Correct.
4 Correct 19 ms 6448 KB Correct.
5 Correct 26 ms 6480 KB Correct.
6 Correct 27 ms 11604 KB Correct.
7 Correct 27 ms 11604 KB Correct.
8 Correct 16 ms 16988 KB Correct.
9 Correct 18 ms 5860 KB Correct.
10 Correct 18 ms 5980 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6492 KB Correct.
2 Correct 21 ms 6492 KB Correct.
3 Correct 21 ms 6492 KB Correct.
4 Correct 19 ms 5980 KB Correct.
5 Correct 19 ms 5976 KB Correct.
6 Correct 7 ms 10076 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 40020 KB Correct.
2 Correct 171 ms 6480 KB Correct.
3 Correct 157 ms 6596 KB Correct.
4 Correct 163 ms 6480 KB Correct.
5 Correct 144 ms 6068 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6492 KB Correct.
2 Correct 20 ms 6492 KB Correct.
3 Correct 18 ms 6448 KB Correct.
4 Correct 20 ms 11644 KB Correct.
5 Correct 15 ms 5980 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6628 KB Correct.
2 Correct 16 ms 6624 KB Correct.
3 Correct 48 ms 50556 KB Correct.
4 Correct 16 ms 9820 KB Correct.
5 Correct 18 ms 5896 KB Correct.
6 Correct 18 ms 6496 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 6996 KB Correct.
2 Correct 29 ms 7328 KB Correct.
3 Correct 529 ms 64200 KB Correct.
4 Correct 434 ms 19540 KB Correct.
5 Correct 662 ms 62364 KB Correct.
6 Correct 320 ms 32596 KB Correct.
7 Correct 458 ms 20496 KB Correct.
8 Correct 451 ms 8560 KB Correct.
9 Correct 168 ms 7060 KB Correct.
10 Correct 172 ms 7464 KB Correct.
11 Correct 452 ms 7120 KB Correct.
12 Correct 172 ms 7308 KB Correct.
13 Correct 198 ms 7304 KB Correct.
14 Correct 380 ms 34808 KB Correct.
15 Correct 461 ms 13912 KB Correct.
16 Correct 164 ms 7068 KB Correct.
17 Correct 200 ms 7116 KB Correct.
18 Correct 201 ms 7084 KB Correct.
19 Correct 469 ms 7468 KB Correct.
20 Correct 16 ms 5464 KB Correct.
21 Correct 16 ms 6016 KB Correct.
22 Correct 27 ms 8400 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 8408 KB Correct.
2 Correct 76 ms 9332 KB Correct.
3 Incorrect 472 ms 64540 KB Wrong Answer.
4 Halted 0 ms 0 KB -