oj.uz

Submission #1094134

# Submission time Handle Problem Language Result Execution time Memory
1094134 2024-09-28T15:08:52 Z RiverFlow Cyberland (APIO23_cyberland) C++17
97 / 100
 646 ms 54424 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 = 32;
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]);
    }

    if (k <= 30) {
        return SUB1::sol();
    }

    return 0;
}


/*     Let the river flows naturally     */

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6232 KB Correct.
2 Correct 19 ms 6492 KB Correct.
3 Correct 23 ms 6484 KB Correct.
4 Correct 18 ms 6492 KB Correct.
5 Correct 19 ms 6488 KB Correct.
6 Correct 23 ms 9304 KB Correct.
7 Correct 23 ms 9564 KB Correct.
8 Correct 22 ms 12044 KB Correct.
9 Correct 18 ms 5980 KB Correct.
10 Correct 17 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 22 ms 6496 KB Correct.
3 Correct 19 ms 6488 KB Correct.
4 Correct 20 ms 5984 KB Correct.
5 Correct 19 ms 5984 KB Correct.
6 Correct 8 ms 7972 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 25632 KB Correct.
2 Correct 172 ms 6488 KB Correct.
3 Correct 165 ms 6484 KB Correct.
4 Correct 153 ms 6484 KB Correct.
5 Correct 148 ms 6140 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6488 KB Correct.
2 Correct 33 ms 6492 KB Correct.
3 Correct 20 ms 6492 KB Correct.
4 Correct 19 ms 9392 KB Correct.
5 Correct 17 ms 5980 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6492 KB Correct.
2 Correct 16 ms 6488 KB Correct.
3 Correct 43 ms 32220 KB Correct.
4 Correct 19 ms 8284 KB Correct.
5 Correct 17 ms 6028 KB Correct.
6 Correct 18 ms 6492 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 7008 KB Correct.
2 Correct 27 ms 6808 KB Correct.
3 Correct 546 ms 41376 KB Correct.
4 Correct 454 ms 15076 KB Correct.
5 Correct 646 ms 54424 KB Correct.
6 Correct 312 ms 30640 KB Correct.
7 Correct 439 ms 15404 KB Correct.
8 Correct 443 ms 8512 KB Correct.
9 Correct 174 ms 7172 KB Correct.
10 Correct 183 ms 7240 KB Correct.
11 Correct 433 ms 7636 KB Correct.
12 Correct 173 ms 7156 KB Correct.
13 Correct 186 ms 7300 KB Correct.
14 Correct 375 ms 23876 KB Correct.
15 Correct 446 ms 11612 KB Correct.
16 Correct 168 ms 7092 KB Correct.
17 Correct 198 ms 7116 KB Correct.
18 Correct 202 ms 7008 KB Correct.
19 Correct 453 ms 7968 KB Correct.
20 Correct 16 ms 5468 KB Correct.
21 Correct 15 ms 5760 KB Correct.
22 Correct 27 ms 8088 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 6236 KB Wrong Answer.
2 Halted 0 ms 0 KB -