oj.uz

Submission #983933

# Submission time Handle Problem Language Result Execution time Memory
983933 2024-05-16T08:13:16 Z Shayan86 Cyberland (APIO23_cyberland) C++17
15 / 100
 938 ms 82836 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;
    for(int i = 0; i < n; i++) if(!a[i] && mark[i]){
        dist[i][0] = 0; pq.push({{0, dist[i][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;
                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<ld, pii>, vector<pair<ld, pii>>, greater<pair<ld, pii>>> pq;
    for(int i = 0; i < n; i++) if(i != H && mark[i]){
        dist[i][0] = 0; pq.push({dist[i][0], {i, 0}});
    }

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

        if(vd != dist[v][id]) continue;

        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;
                pq.push({dist[u][id], {u, id}});
            }
            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({dist[u][id+1], {u, id+1}});
            }
        }
    }
}

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
0.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 4948 KB Correct.
2 Correct 278 ms 5008 KB Correct.
3 Correct 266 ms 4980 KB Correct.
4 Correct 276 ms 4948 KB Correct.
5 Correct 275 ms 5020 KB Correct.
6 Correct 291 ms 17004 KB Correct.
7 Correct 370 ms 16880 KB Correct.
8 Correct 170 ms 28628 KB Correct.
9 Correct 197 ms 4696 KB Correct.
10 Correct 194 ms 4696 KB Correct.

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 19.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 4956 KB Correct.
2 Correct 107 ms 4952 KB Correct.
3 Correct 116 ms 5052 KB Correct.
4 Correct 144 ms 16716 KB Correct.
5 Correct 75 ms 4796 KB Correct.

Subtask #6
0.0 / 16.0

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

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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