oj.uz

Submission #1095132

# Submission time Handle Problem Language Result Execution time Memory
1095132 2024-10-01T11:06:02 Z RiverFlow Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 97908 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 = 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 16 ms 5468 KB Correct.
2 Correct 15 ms 5468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6736 KB Correct.
2 Correct 25 ms 6876 KB Correct.
3 Correct 19 ms 6748 KB Correct.
4 Correct 20 ms 6744 KB Correct.
5 Correct 19 ms 6748 KB Correct.
6 Correct 20 ms 12124 KB Correct.
7 Correct 25 ms 12372 KB Correct.
8 Correct 17 ms 18012 KB Correct.
9 Correct 17 ms 5980 KB Correct.
10 Correct 17 ms 6144 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6748 KB Correct.
2 Correct 21 ms 6748 KB Correct.
3 Correct 20 ms 6744 KB Correct.
4 Correct 22 ms 5976 KB Correct.
5 Correct 19 ms 6196 KB Correct.
6 Correct 9 ms 10332 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 43344 KB Correct.
2 Correct 176 ms 6736 KB Correct.
3 Correct 149 ms 6864 KB Correct.
4 Correct 160 ms 6736 KB Correct.
5 Correct 146 ms 6176 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 20 ms 6892 KB Correct.
4 Correct 21 ms 12376 KB Correct.
5 Correct 16 ms 5980 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7256 KB Correct.
2 Correct 25 ms 6748 KB Correct.
3 Correct 49 ms 55384 KB Correct.
4 Correct 15 ms 10332 KB Correct.
5 Correct 18 ms 6136 KB Correct.
6 Correct 18 ms 6748 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 7264 KB Correct.
2 Correct 28 ms 7328 KB Correct.
3 Correct 548 ms 70380 KB Correct.
4 Correct 442 ms 21688 KB Correct.
5 Correct 708 ms 65180 KB Correct.
6 Correct 317 ms 33572 KB Correct.
7 Correct 445 ms 22452 KB Correct.
8 Correct 467 ms 9392 KB Correct.
9 Correct 176 ms 7320 KB Correct.
10 Correct 168 ms 7492 KB Correct.
11 Correct 435 ms 7888 KB Correct.
12 Correct 173 ms 7520 KB Correct.
13 Correct 194 ms 7864 KB Correct.
14 Correct 378 ms 37964 KB Correct.
15 Correct 458 ms 15192 KB Correct.
16 Correct 179 ms 7364 KB Correct.
17 Correct 201 ms 7372 KB Correct.
18 Correct 203 ms 7280 KB Correct.
19 Correct 479 ms 7948 KB Correct.
20 Correct 16 ms 5420 KB Correct.
21 Correct 16 ms 6104 KB Correct.
22 Correct 31 ms 8612 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 8640 KB Correct.
2 Correct 87 ms 9464 KB Correct.
3 Correct 526 ms 71104 KB Correct.
4 Correct 979 ms 12696 KB Correct.
5 Correct 2340 ms 97908 KB Correct.
6 Correct 1221 ms 82952 KB Correct.
7 Correct 1081 ms 36776 KB Correct.
8 Correct 1191 ms 9284 KB Correct.
9 Correct 609 ms 10192 KB Correct.
10 Correct 623 ms 10028 KB Correct.
11 Execution timed out 3044 ms 6228 KB Time limit exceeded
12 Halted 0 ms 0 KB -