oj.uz

Submission #1095134

# Submission time Handle Problem Language Result Execution time Memory
1095134 2024-10-01T11:09:47 Z RiverFlow Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 97912 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-6;
namespace SUB1 {
const int K = 71;
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, 69);
  
    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 15 ms 5464 KB Correct.
2 Correct 16 ms 5468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6748 KB Correct.
2 Correct 20 ms 6724 KB Correct.
3 Correct 21 ms 6748 KB Correct.
4 Correct 26 ms 6748 KB Correct.
5 Correct 22 ms 6712 KB Correct.
6 Correct 23 ms 12380 KB Correct.
7 Correct 27 ms 12380 KB Correct.
8 Correct 17 ms 18012 KB Correct.
9 Correct 19 ms 5980 KB Correct.
10 Correct 18 ms 5980 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6748 KB Correct.
2 Correct 20 ms 6744 KB Correct.
3 Correct 20 ms 6748 KB Correct.
4 Correct 19 ms 5980 KB Correct.
5 Correct 18 ms 5980 KB Correct.
6 Correct 8 ms 10332 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 43356 KB Correct.
2 Correct 173 ms 6736 KB Correct.
3 Correct 150 ms 6828 KB Correct.
4 Correct 154 ms 6736 KB Correct.
5 Correct 145 ms 6048 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6744 KB Correct.
2 Correct 18 ms 6748 KB Correct.
3 Correct 18 ms 6764 KB Correct.
4 Correct 27 ms 12628 KB Correct.
5 Correct 16 ms 5976 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6744 KB Correct.
2 Correct 16 ms 6744 KB Correct.
3 Correct 44 ms 55384 KB Correct.
4 Correct 17 ms 10332 KB Correct.
5 Correct 18 ms 5980 KB Correct.
6 Correct 23 ms 6744 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 7220 KB Correct.
2 Correct 27 ms 7332 KB Correct.
3 Correct 575 ms 70436 KB Correct.
4 Correct 438 ms 21680 KB Correct.
5 Correct 633 ms 65176 KB Correct.
6 Correct 336 ms 33712 KB Correct.
7 Correct 443 ms 22684 KB Correct.
8 Correct 440 ms 9528 KB Correct.
9 Correct 172 ms 7232 KB Correct.
10 Correct 181 ms 7504 KB Correct.
11 Correct 433 ms 7892 KB Correct.
12 Correct 178 ms 7668 KB Correct.
13 Correct 189 ms 7636 KB Correct.
14 Correct 386 ms 37960 KB Correct.
15 Correct 457 ms 15444 KB Correct.
16 Correct 168 ms 7364 KB Correct.
17 Correct 199 ms 7356 KB Correct.
18 Correct 201 ms 7384 KB Correct.
19 Correct 458 ms 8244 KB Correct.
20 Correct 15 ms 5468 KB Correct.
21 Correct 15 ms 6228 KB Correct.
22 Correct 28 ms 8556 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 8888 KB Correct.
2 Correct 82 ms 9520 KB Correct.
3 Correct 575 ms 71348 KB Correct.
4 Correct 975 ms 12756 KB Correct.
5 Correct 2327 ms 97912 KB Correct.
6 Correct 1189 ms 82808 KB Correct.
7 Correct 1062 ms 36884 KB Correct.
8 Correct 1175 ms 8944 KB Correct.
9 Correct 616 ms 10224 KB Correct.
10 Correct 607 ms 10032 KB Correct.
11 Execution timed out 3068 ms 6256 KB Time limit exceeded
12 Halted 0 ms 0 KB -