oj.uz

Submission #1095130

# Submission time Handle Problem Language Result Execution time Memory
1095130 2024-10-01T11:04:31 Z RiverFlow Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 69704 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 = 70;
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) {
 
    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 5588 KB Correct.
2 Correct 16 ms 5468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6744 KB Correct.
2 Correct 21 ms 6744 KB Correct.
3 Correct 18 ms 6748 KB Correct.
4 Correct 19 ms 6748 KB Correct.
5 Correct 22 ms 6744 KB Correct.
6 Correct 19 ms 12124 KB Correct.
7 Correct 24 ms 12380 KB Correct.
8 Correct 17 ms 18012 KB Correct.
9 Correct 17 ms 6016 KB Correct.
10 Correct 18 ms 6132 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6744 KB Correct.
2 Correct 30 ms 6572 KB Correct.
3 Correct 19 ms 6748 KB Correct.
4 Correct 19 ms 5976 KB Correct.
5 Correct 18 ms 5980 KB Correct.
6 Correct 7 ms 10332 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 43048 KB Correct.
2 Correct 176 ms 6756 KB Correct.
3 Correct 147 ms 6700 KB Correct.
4 Correct 153 ms 6740 KB Correct.
5 Correct 145 ms 5968 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6748 KB Correct.
2 Correct 17 ms 6924 KB Correct.
3 Correct 19 ms 6748 KB Correct.
4 Correct 24 ms 12336 KB Correct.
5 Correct 15 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 17 ms 6744 KB Correct.
3 Correct 44 ms 54612 KB Correct.
4 Correct 15 ms 10332 KB Correct.
5 Correct 17 ms 5980 KB Correct.
6 Correct 17 ms 6660 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 7288 KB Correct.
2 Correct 28 ms 7328 KB Correct.
3 Correct 523 ms 69704 KB Correct.
4 Correct 436 ms 21456 KB Correct.
5 Correct 621 ms 64920 KB Correct.
6 Correct 327 ms 33480 KB Correct.
7 Correct 449 ms 22372 KB Correct.
8 Correct 441 ms 9408 KB Correct.
9 Correct 169 ms 7296 KB Correct.
10 Correct 171 ms 7500 KB Correct.
11 Correct 436 ms 7892 KB Correct.
12 Correct 176 ms 7664 KB Correct.
13 Correct 184 ms 7704 KB Correct.
14 Correct 372 ms 37704 KB Correct.
15 Correct 451 ms 15192 KB Correct.
16 Correct 163 ms 7368 KB Correct.
17 Correct 202 ms 7364 KB Correct.
18 Correct 199 ms 7388 KB Correct.
19 Correct 458 ms 8276 KB Correct.
20 Correct 16 ms 5720 KB Correct.
21 Correct 16 ms 6104 KB Correct.
22 Correct 27 ms 8400 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3047 ms 30320 KB Time limit exceeded
2 Halted 0 ms 0 KB -