oj.uz

Submission #983964

# Submission time Handle Problem Language Result Execution time Memory
983964 2024-05-16T08:35:00 Z Shayan86 Cyberland (APIO23_cyberland) C++17
97 / 100
 1355 ms 168400 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 = 100;
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 && mark[i] && a[i] != 1){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(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){
        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 37 ms 4700 KB Correct.
2 Correct 35 ms 4700 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 4944 KB Correct.
2 Correct 284 ms 5464 KB Correct.
3 Correct 264 ms 5004 KB Correct.
4 Correct 274 ms 4916 KB Correct.
5 Correct 274 ms 5200 KB Correct.
6 Correct 321 ms 21060 KB Correct.
7 Correct 387 ms 21000 KB Correct.
8 Correct 169 ms 38868 KB Correct.
9 Correct 207 ms 5040 KB Correct.
10 Correct 193 ms 4696 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 5000 KB Correct.
2 Correct 277 ms 5236 KB Correct.
3 Correct 246 ms 5012 KB Correct.
4 Correct 207 ms 4780 KB Correct.
5 Correct 206 ms 4696 KB Correct.
6 Correct 68 ms 18520 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 102476 KB Correct.
2 Correct 240 ms 4996 KB Correct.
3 Correct 187 ms 5036 KB Correct.
4 Correct 204 ms 5264 KB Correct.
5 Correct 147 ms 4700 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 4948 KB Correct.
2 Correct 128 ms 5072 KB Correct.
3 Correct 120 ms 5228 KB Correct.
4 Correct 147 ms 20752 KB Correct.
5 Correct 74 ms 4696 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 5088 KB Correct.
2 Correct 89 ms 4984 KB Correct.
3 Correct 32 ms 11600 KB Correct.
4 Correct 91 ms 14636 KB Correct.
5 Correct 90 ms 4788 KB Correct.
6 Correct 107 ms 4984 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 5024 KB Correct.
2 Correct 33 ms 5172 KB Correct.
3 Correct 1355 ms 168400 KB Correct.
4 Correct 717 ms 42652 KB Correct.
5 Correct 675 ms 70676 KB Correct.
6 Correct 299 ms 26580 KB Correct.
7 Correct 661 ms 47164 KB Correct.
8 Correct 529 ms 9772 KB Correct.
9 Correct 159 ms 5176 KB Correct.
10 Correct 138 ms 5088 KB Correct.
11 Correct 477 ms 7260 KB Correct.
12 Correct 171 ms 4952 KB Correct.
13 Correct 172 ms 5144 KB Correct.
14 Correct 601 ms 84928 KB Correct.
15 Correct 573 ms 26208 KB Correct.
16 Correct 154 ms 4952 KB Correct.
17 Correct 194 ms 5120 KB Correct.
18 Correct 171 ms 5140 KB Correct.
19 Correct 444 ms 5060 KB Correct.
20 Correct 11 ms 4700 KB Correct.
21 Correct 12 ms 4700 KB Correct.
22 Correct 25 ms 5660 KB Correct.

Subtask #8
0.0 / 3.0

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