oj.uz

Submission #983942

# Submission time Handle Problem Language Result Execution time Memory
983942 2024-05-16T08:19:50 Z Shayan86 Cyberland (APIO23_cyberland) C++17
97 / 100
 1227 ms 127736 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});
            }
        }
    }
}

void dijk2(){
    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;
    for(int i = 0; i < n; i++) if(i != H){dist[i][0] = 0; pq.push({{0, 0}, i});}

    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 34 ms 4700 KB Correct.
2 Correct 34 ms 4696 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 4944 KB Correct.
2 Correct 280 ms 5200 KB Correct.
3 Correct 304 ms 4904 KB Correct.
4 Correct 276 ms 4948 KB Correct.
5 Correct 279 ms 5200 KB Correct.
6 Correct 275 ms 16996 KB Correct.
7 Correct 374 ms 16868 KB Correct.
8 Correct 164 ms 28624 KB Correct.
9 Correct 197 ms 4696 KB Correct.
10 Correct 195 ms 4696 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 5024 KB Correct.
2 Correct 268 ms 5052 KB Correct.
3 Correct 245 ms 5016 KB Correct.
4 Correct 207 ms 4784 KB Correct.
5 Correct 207 ms 4788 KB Correct.
6 Correct 64 ms 14420 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 78068 KB Correct.
2 Correct 213 ms 4996 KB Correct.
3 Correct 185 ms 4956 KB Correct.
4 Correct 198 ms 4956 KB Correct.
5 Correct 145 ms 4792 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 5220 KB Correct.
2 Correct 106 ms 4964 KB Correct.
3 Correct 116 ms 4956 KB Correct.
4 Correct 145 ms 16652 KB Correct.
5 Correct 76 ms 4780 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 5000 KB Correct.
2 Correct 89 ms 4956 KB Correct.
3 Correct 32 ms 11612 KB Correct.
4 Correct 87 ms 12600 KB Correct.
5 Correct 90 ms 4788 KB Correct.
6 Correct 106 ms 4956 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 5128 KB Correct.
2 Correct 28 ms 5168 KB Correct.
3 Correct 1227 ms 127736 KB Correct.
4 Correct 715 ms 32612 KB Correct.
5 Correct 677 ms 53704 KB Correct.
6 Correct 289 ms 22484 KB Correct.
7 Correct 657 ms 36668 KB Correct.
8 Correct 532 ms 7792 KB Correct.
9 Correct 157 ms 5180 KB Correct.
10 Correct 155 ms 4952 KB Correct.
11 Correct 475 ms 5544 KB Correct.
12 Correct 171 ms 4948 KB Correct.
13 Correct 175 ms 5020 KB Correct.
14 Correct 603 ms 64840 KB Correct.
15 Correct 539 ms 19976 KB Correct.
16 Correct 159 ms 5240 KB Correct.
17 Correct 197 ms 5064 KB Correct.
18 Correct 175 ms 4948 KB Correct.
19 Correct 452 ms 5060 KB Correct.
20 Correct 11 ms 4700 KB Correct.
21 Correct 12 ms 4700 KB Correct.
22 Correct 23 ms 5664 KB Correct.

Subtask #8
0.0 / 3.0

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