oj.uz

Submission #1095155

# Submission time Handle Problem Language Result Execution time Memory
1095155 2024-10-01T12:49:35 Z RiverFlow Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 94776 KB 
#include "cyberland.h"
                
#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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)1e5 + 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 = 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;
        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     */

Compilation message

cyberland.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
cyberland.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4696 KB Correct.
2 Correct 14 ms 4580 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5212 KB Correct.
2 Correct 17 ms 4764 KB Correct.
3 Correct 18 ms 4744 KB Correct.
4 Correct 17 ms 4700 KB Correct.
5 Correct 17 ms 4696 KB Correct.
6 Correct 17 ms 10588 KB Correct.
7 Correct 20 ms 10480 KB Correct.
8 Correct 12 ms 16472 KB Correct.
9 Correct 15 ms 4440 KB Correct.
10 Correct 15 ms 4444 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4700 KB Correct.
2 Correct 26 ms 5208 KB Correct.
3 Correct 18 ms 5212 KB Correct.
4 Correct 17 ms 4184 KB Correct.
5 Correct 17 ms 4168 KB Correct.
6 Correct 6 ms 9052 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 40760 KB Correct.
2 Correct 170 ms 4700 KB Correct.
3 Correct 147 ms 4700 KB Correct.
4 Correct 151 ms 6888 KB Correct.
5 Correct 142 ms 4952 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5208 KB Correct.
2 Correct 17 ms 4820 KB Correct.
3 Correct 21 ms 5468 KB Correct.
4 Correct 18 ms 10332 KB Correct.
5 Correct 14 ms 4180 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4700 KB Correct.
2 Correct 15 ms 4700 KB Correct.
3 Correct 42 ms 51824 KB Correct.
4 Correct 15 ms 9048 KB Correct.
5 Correct 16 ms 4440 KB Correct.
6 Correct 16 ms 4700 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 5584 KB Correct.
2 Correct 26 ms 6548 KB Correct.
3 Correct 519 ms 66212 KB Correct.
4 Correct 441 ms 18360 KB Correct.
5 Correct 614 ms 62368 KB Correct.
6 Correct 301 ms 31420 KB Correct.
7 Correct 438 ms 19788 KB Correct.
8 Correct 429 ms 7240 KB Correct.
9 Correct 170 ms 7660 KB Correct.
10 Correct 166 ms 5656 KB Correct.
11 Correct 432 ms 5060 KB Correct.
12 Correct 171 ms 7664 KB Correct.
13 Correct 181 ms 7700 KB Correct.
14 Correct 386 ms 34372 KB Correct.
15 Correct 443 ms 12632 KB Correct.
16 Correct 161 ms 5480 KB Correct.
17 Correct 204 ms 5824 KB Correct.
18 Correct 198 ms 7528 KB Correct.
19 Correct 452 ms 7432 KB Correct.
20 Correct 16 ms 4184 KB Correct.
21 Correct 14 ms 5516 KB Correct.
22 Correct 25 ms 7120 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 7416 KB Correct.
2 Correct 81 ms 8200 KB Correct.
3 Correct 548 ms 65444 KB Correct.
4 Correct 952 ms 9824 KB Correct.
5 Correct 2238 ms 94776 KB Correct.
6 Correct 1185 ms 80244 KB Correct.
7 Correct 1041 ms 33304 KB Correct.
8 Correct 1157 ms 7976 KB Correct.
9 Correct 597 ms 8676 KB Correct.
10 Correct 596 ms 10292 KB Correct.
11 Execution timed out 3048 ms 4688 KB Time limit exceeded
12 Halted 0 ms 0 KB -