oj.uz

Submission #983938

# Submission time Handle Problem Language Result Execution time Memory
983938 2024-05-16T08:17:59 Z Shayan86 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 136616 KB 
//#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define SZ(x)       (int)x.size()
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll K = 72;
const ll N = 1e5 + 50;
const ll inf = 1e18;

ll n, m, k, H, a[N];
ld dist[N][K];

bool mark[N];
vector<pll> adj[N];

void dfs(int v){
    mark[v] = true;
    for(auto [u, w]: adj[v]) if(!mark[u]) dfs(u);
}

void dijk(){
    for(int i = 0; i < n; i++) for(int j = 0; j <= k; j++) dist[i][j] = inf;

    priority_queue<pair<pair<int, ld>, int>, vector<pair<pair<int, ld>, int>>, greater<pair<pair<int, ld>, int>>> pq;
    dist[0][0] = 0; pq.push({{0, 0}, 0});

    while (!pq.empty()){
        auto [id, vd] = pq.top().F;
        auto v = pq.top().S;
        pq.pop();

        if(id < k){
            if(dist[v][id+1] > dist[v][id]){
                dist[v][id+1] = dist[v][id];
                pq.push({{id+1, dist[v][id+1]}, v});
            }
        }

        if(v == H) continue;

        for (auto [u, w]: adj[v]){
            if(dist[u][id] > dist[v][id] + w){
                dist[u][id] = dist[v][id] + w;
                if(a[u] == 0) dist[u][id] = 0;
                pq.push({{id, dist[u][id]}, u});
            }
            if(a[u] != 2 || id == k) continue;
            if(dist[u][id+1] * 2 > dist[v][id] + w){
                dist[u][id+1] = dist[v][id] + w; dist[u][id+1] /= 2;
                pq.push({{id+1, dist[u][id+1]}, u});
            }
        }
    }
}

double solve(int N, int M, int Kk, int H_, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    n = N; m = M; k = Kk; H = H_;

    for(int i = 0; i < n; i++){
        adj[i].clear(); mark[i] = false;
    }

    for(int i = 0; i < m; i++){
        int u = x[i];
        int v = y[i];
        int w = c[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }

    for(int i = 0; i < n; i++) a[i] = arr[i];

    dfs(0);
    if(!mark[H]) return -1;

    k = min(k, 70ll);
    a[0] = 0; dijk();

    ld res = dist[H][k];
/*
    if(Kk > k){
        k++; dijk2();
        res = min(res, dist[H][k]);
    }
*/

    if(res >= inf) return -1;
    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4696 KB Correct.
2 Correct 36 ms 4952 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 4948 KB Correct.
2 Correct 290 ms 5216 KB Correct.
3 Correct 267 ms 5204 KB Correct.
4 Correct 275 ms 4996 KB Correct.
5 Correct 278 ms 4988 KB Correct.
6 Correct 276 ms 16952 KB Correct.
7 Correct 367 ms 16868 KB Correct.
8 Correct 171 ms 28628 KB Correct.
9 Correct 197 ms 4696 KB Correct.
10 Correct 197 ms 4784 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 5004 KB Correct.
2 Correct 271 ms 5880 KB Correct.
3 Correct 252 ms 5700 KB Correct.
4 Correct 209 ms 5668 KB Correct.
5 Correct 207 ms 5456 KB Correct.
6 Correct 63 ms 14680 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 78028 KB Correct.
2 Correct 211 ms 6012 KB Correct.
3 Correct 189 ms 5976 KB Correct.
4 Correct 199 ms 5872 KB Correct.
5 Correct 149 ms 5660 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 4956 KB Correct.
2 Correct 107 ms 4952 KB Correct.
3 Correct 119 ms 4956 KB Correct.
4 Correct 147 ms 16748 KB Correct.
5 Correct 76 ms 4784 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 4972 KB Correct.
2 Correct 91 ms 5972 KB Correct.
3 Correct 33 ms 13396 KB Correct.
4 Correct 97 ms 13204 KB Correct.
5 Correct 92 ms 5988 KB Correct.
6 Correct 107 ms 6036 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 4944 KB Correct.
2 Correct 28 ms 5212 KB Correct.
3 Correct 1322 ms 129740 KB Correct.
4 Correct 714 ms 34744 KB Correct.
5 Correct 745 ms 56972 KB Correct.
6 Correct 291 ms 24020 KB Correct.
7 Correct 674 ms 38696 KB Correct.
8 Correct 522 ms 9460 KB Correct.
9 Correct 157 ms 6020 KB Correct.
10 Correct 139 ms 5816 KB Correct.
11 Correct 492 ms 7016 KB Correct.
12 Correct 173 ms 6064 KB Correct.
13 Correct 174 ms 6080 KB Correct.
14 Correct 576 ms 66644 KB Correct.
15 Correct 572 ms 21804 KB Correct.
16 Correct 155 ms 5928 KB Correct.
17 Correct 200 ms 6144 KB Correct.
18 Correct 173 ms 5968 KB Correct.
19 Correct 462 ms 7080 KB Correct.
20 Correct 11 ms 4700 KB Correct.
21 Correct 13 ms 4848 KB Correct.
22 Correct 27 ms 5724 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 5064 KB Correct.
2 Correct 59 ms 5208 KB Correct.
3 Execution timed out 3031 ms 136616 KB Time limit exceeded
4 Halted 0 ms 0 KB -