oj.uz

Submission #1095152

# Submission time Handle Problem Language Result Execution time Memory
1095152 2024-10-01T12:48:07 Z RiverFlow Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 98768 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;
        if (u == h) continue ;
      	if (x.fi != dis[u][t]) 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 14 ms 6748 KB Correct.
2 Correct 14 ms 5468 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5980 KB Correct.
2 Correct 17 ms 5976 KB Correct.
3 Correct 17 ms 5976 KB Correct.
4 Correct 17 ms 5980 KB Correct.
5 Correct 17 ms 6016 KB Correct.
6 Correct 18 ms 11556 KB Correct.
7 Correct 21 ms 12664 KB Correct.
8 Correct 13 ms 18780 KB Correct.
9 Correct 15 ms 6732 KB Correct.
10 Correct 15 ms 5452 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5980 KB Correct.
2 Correct 19 ms 7004 KB Correct.
3 Correct 18 ms 7004 KB Correct.
4 Correct 18 ms 6320 KB Correct.
5 Correct 18 ms 6332 KB Correct.
6 Correct 7 ms 10588 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 42320 KB Correct.
2 Correct 178 ms 5980 KB Correct.
3 Correct 148 ms 6888 KB Correct.
4 Correct 152 ms 9820 KB Correct.
5 Correct 144 ms 7492 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5980 KB Correct.
2 Correct 16 ms 5980 KB Correct.
3 Correct 16 ms 5980 KB Correct.
4 Correct 18 ms 11612 KB Correct.
5 Correct 14 ms 6708 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8796 KB Correct.
2 Correct 16 ms 9820 KB Correct.
3 Correct 50 ms 55564 KB Correct.
4 Correct 14 ms 10584 KB Correct.
5 Correct 15 ms 7516 KB Correct.
6 Correct 17 ms 9820 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 9696 KB Correct.
2 Correct 28 ms 10392 KB Correct.
3 Correct 513 ms 70816 KB Correct.
4 Correct 439 ms 22712 KB Correct.
5 Correct 619 ms 65944 KB Correct.
6 Correct 300 ms 34740 KB Correct.
7 Correct 440 ms 23852 KB Correct.
8 Correct 429 ms 11288 KB Correct.
9 Correct 167 ms 7544 KB Correct.
10 Correct 165 ms 10596 KB Correct.
11 Correct 431 ms 10964 KB Correct.
12 Correct 175 ms 8048 KB Correct.
13 Correct 183 ms 10644 KB Correct.
14 Correct 374 ms 38728 KB Correct.
15 Correct 449 ms 16744 KB Correct.
16 Correct 163 ms 10436 KB Correct.
17 Correct 200 ms 10416 KB Correct.
18 Correct 204 ms 7536 KB Correct.
19 Correct 455 ms 11348 KB Correct.
20 Correct 15 ms 5724 KB Correct.
21 Correct 15 ms 6300 KB Correct.
22 Correct 27 ms 8656 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 10952 KB Correct.
2 Correct 81 ms 12136 KB Correct.
3 Correct 511 ms 71504 KB Correct.
4 Correct 962 ms 14344 KB Correct.
5 Correct 2255 ms 98768 KB Correct.
6 Correct 1228 ms 83828 KB Correct.
7 Correct 1055 ms 37500 KB Correct.
8 Correct 1154 ms 11996 KB Correct.
9 Correct 629 ms 11984 KB Correct.
10 Correct 607 ms 10788 KB Correct.
11 Execution timed out 3034 ms 7644 KB Time limit exceeded
12 Halted 0 ms 0 KB -