oj.uz

Submission #969947

# Submission time Handle Problem Language Result Execution time Memory
969947 2024-04-26T01:21:17 Z Br3ad Cyberland (APIO23_cyberland) C++17
100 / 100
 194 ms 71064 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)

const int N = 1e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const double INF = 1e18;

// Make variable global 
vector<vector<pair<int, int>>> adj(N, vector<pair<int, int>>());
vector<int> canUse(N, false);

void init(int n){
    adj.clear();
    adj.resize(n, vector<pair<int, int>>());
    for(int i = 0; i < n; i++) canUse[i] = false;
}

void dfs(int cur, int h){
    if(cur == h) return;
    canUse[cur] = true;
    for(pair<int, int> p : adj[cur]){
        if(!canUse[p.f]) dfs(p.f, h);
    }
    
}

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
    init(n);
    for(int i = 0; i < m; i++){
        adj[x[i]].PB(MP(y[i], c[i]));
        adj[y[i]].PB(MP(x[i], c[i]));
    }

    dfs(0, h);
    arr[0] = 0;
    k = min(k, 69);

    vector<double> half(k+1, 1);
    for(int i = 1; i <= k; i++){
        half[i] = half[i-1]/2;
    }

    using node = tuple<double, int, int>;
    priority_queue<node, vector<node>, greater<node>> pq;
    vector<vector<double>> dis(n, vector<double>(k+1, 1e18));
    
    auto query = [&](int id, int use, double time){
        if(dis[id][use] > time){
            dis[id][use] = time;
            pq.push((node)make_tuple(time, use, id));
        }
    };

    query(h, k, 0);
    while(!pq.empty()){
        auto [time, use, id] = pq.top();
        pq.pop();
        
        if(dis[id][use] < time) continue;
        if(arr[id] == 0) return time;
        
        for(pair<int, int> p : adj[id]){
            if(!canUse[p.f]) continue;
            // Didnt use ability
            query(p.f, use, time + (double)p.s * half[k - use]);

            // Use ability
            if(arr[id] == 2 && use > 0) query(p.f, use-1, time + (double)p.s * half[k - use + 1]);
        }
    }

    return -1;
}

// int main(){
    
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
    
//     // ifstream cin();
//     // ofstream cout();
    
//     cout << solve(4, 3, 30, 3, {3, 2, 1}, {1, 1, 0}, {2, 3, 5}, {1, 1, 0, 1}) << endl;
//     cout << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << endl;
//     cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << endl;
    
// }

// Foot Note:
// Approach for general solution with ability constraint(K <= 30)
// Using BFS (Multisource BFS)

/****Observation****/
// There's no point revisiting node '0' ability (Can be used as starting point)

/****Implementation****/
// Let accessible node i where arr[i] = 0 be starting point (multisource BFS)
// Save three value in queue <node, ability, time>
// When visiting a node, update state and push updated result


/****Potential Technic for Subtask 7 (K <= 1e6)****/
// Hypothesis: There exists a maximum Kmax, which any extra operation after Kmax is seemlessly effective

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3416 KB Correct.
2 Correct 19 ms 3672 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3416 KB Correct.
2 Correct 24 ms 3420 KB Correct.
3 Correct 20 ms 3536 KB Correct.
4 Correct 21 ms 3572 KB Correct.
5 Correct 20 ms 3672 KB Correct.
6 Correct 18 ms 6544 KB Correct.
7 Correct 23 ms 6296 KB Correct.
8 Correct 11 ms 9820 KB Correct.
9 Correct 25 ms 3420 KB Correct.
10 Correct 23 ms 4184 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3416 KB Correct.
2 Correct 21 ms 3528 KB Correct.
3 Correct 19 ms 3600 KB Correct.
4 Correct 20 ms 3420 KB Correct.
5 Correct 21 ms 4188 KB Correct.
6 Correct 6 ms 6052 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23056 KB Correct.
2 Correct 20 ms 3420 KB Correct.
3 Correct 19 ms 3624 KB Correct.
4 Correct 21 ms 3776 KB Correct.
5 Correct 21 ms 3280 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3544 KB Correct.
2 Correct 24 ms 3508 KB Correct.
3 Correct 23 ms 3580 KB Correct.
4 Correct 25 ms 6492 KB Correct.
5 Correct 21 ms 3164 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3580 KB Correct.
2 Correct 20 ms 3536 KB Correct.
3 Correct 55 ms 28884 KB Correct.
4 Correct 15 ms 5232 KB Correct.
5 Correct 22 ms 3416 KB Correct.
6 Correct 21 ms 4508 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3572 KB Correct.
2 Correct 4 ms 3676 KB Correct.
3 Correct 48 ms 26780 KB Correct.
4 Correct 40 ms 9180 KB Correct.
5 Correct 34 ms 18012 KB Correct.
6 Correct 25 ms 10076 KB Correct.
7 Correct 43 ms 8892 KB Correct.
8 Correct 41 ms 4124 KB Correct.
9 Correct 24 ms 3764 KB Correct.
10 Correct 20 ms 3532 KB Correct.
11 Correct 42 ms 3568 KB Correct.
12 Correct 20 ms 3548 KB Correct.
13 Correct 21 ms 3528 KB Correct.
14 Correct 45 ms 10612 KB Correct.
15 Correct 39 ms 5144 KB Correct.
16 Correct 27 ms 3536 KB Correct.
17 Correct 23 ms 3544 KB Correct.
18 Correct 22 ms 3544 KB Correct.
19 Correct 38 ms 3444 KB Correct.
20 Correct 4 ms 3164 KB Correct.
21 Correct 3 ms 3464 KB Correct.
22 Correct 4 ms 3676 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3896 KB Correct.
2 Correct 5 ms 4184 KB Correct.
3 Correct 82 ms 71064 KB Correct.
4 Correct 40 ms 5772 KB Correct.
5 Correct 39 ms 29084 KB Correct.
6 Correct 25 ms 13404 KB Correct.
7 Correct 44 ms 15452 KB Correct.
8 Correct 44 ms 4232 KB Correct.
9 Correct 27 ms 3884 KB Correct.
10 Correct 24 ms 3864 KB Correct.
11 Correct 194 ms 4436 KB Correct.
12 Correct 22 ms 4900 KB Correct.
13 Correct 23 ms 4736 KB Correct.
14 Correct 48 ms 31456 KB Correct.
15 Correct 52 ms 37500 KB Correct.
16 Correct 43 ms 15388 KB Correct.
17 Correct 43 ms 7240 KB Correct.
18 Correct 22 ms 4796 KB Correct.
19 Correct 28 ms 4988 KB Correct.
20 Correct 27 ms 4872 KB Correct.
21 Correct 47 ms 5636 KB Correct.
22 Correct 4 ms 3160 KB Correct.
23 Correct 4 ms 3836 KB Correct.
24 Correct 4 ms 4188 KB Correct.