oj.uz

Submission #951171

# Submission time Handle Problem Language Result Execution time Memory
951171 2024-03-21T09:51:53 Z steveonalex Cyberland (APIO23_cyberland) C++17
100 / 100
 897 ms 17156 KB 
#include <bits/stdc++.h>
#include "cyberland.h"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}

ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return __lg(mask);}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }

template <class T>
    void printArr(T& container, char separator = ' ', char finish = '\n'){
        for(auto item: container) cout << item << separator;
        cout << finish;
    }


template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

struct P{
    int i; double w;
    P(){}
    P(int _i, double _w){i = _i, w = _w;}
};

struct compare{
    bool operator () (P a, P b){return a.w > b.w;}
};

const int N = 1e5 + 69;
const int K = 100;
const ll INF = 2e18 + 69;
const double EPS = 1e-6;
int h;
bool visited[N];
double dis[N];
vector<P> graph[N];

void dfs(int u){
    visited[u] = true;
    if (u == h) return;
    for(auto v: graph[u]) if (!visited[v.i]) dfs(v.i);
}

double solve(int n, int m, int k, int _h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    h = _h;
    minimize(k, K);
    for(int i= 0; i<n; ++i){
        graph[i].clear();
        visited[i] = false;
        dis[i] = INF;
    }

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

    dfs(0);
    if (!visited[h]) return -1;

    priority_queue<P, vector<P>, compare> pq;
    for(int i = 0; i<n; ++i) if (visited[i] && (arr[i] == 0 || i == 0)){
        dis[i] = 0;
        pq.push(P(i, 0));
    }

    double ans = INF;
    for(int iteration = 0; iteration <= k; ++iteration){
        if (pq.empty()) break;
        while(pq.size()){
            P u = pq.top(); pq.pop();

            if (u.i == h) continue;
            if (dis[u.i] + EPS < u.w) continue;

            for(P v: graph[u.i]) if (minimize(dis[v.i], dis[u.i] + v.w)) 
                pq.push(P(v.i, dis[v.i]));
        }
        minimize(ans, dis[h]);

        vector<P> yap;
        for(int i = 0; i<n; ++i) if (visited[i]){
            if (arr[i] == 2) yap.push_back(P(i, dis[i] / 2));
            dis[i] = INF;
        }
        for(auto u: yap){
            for(P v: graph[u.i]) minimize(dis[v.i], u.w + v.w);
        }
        for(int i= 0; i<n; ++i) if (visited[i] && dis[i] < INF){
            pq.push(P(i, dis[i]));
        }
    }

    return ans;
}

// int main(void){
    // ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << "\n";

//     return 0;
// }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2908 KB Correct.
2 Correct 15 ms 3164 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2908 KB Correct.
2 Correct 23 ms 2908 KB Correct.
3 Correct 18 ms 2904 KB Correct.
4 Correct 19 ms 2908 KB Correct.
5 Correct 19 ms 2908 KB Correct.
6 Correct 18 ms 3852 KB Correct.
7 Correct 21 ms 3608 KB Correct.
8 Correct 12 ms 4696 KB Correct.
9 Correct 19 ms 2652 KB Correct.
10 Correct 18 ms 2872 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2904 KB Correct.
2 Correct 24 ms 2908 KB Correct.
3 Correct 18 ms 2908 KB Correct.
4 Correct 19 ms 2652 KB Correct.
5 Correct 28 ms 2652 KB Correct.
6 Correct 5 ms 3420 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 8584 KB Correct.
2 Correct 72 ms 3816 KB Correct.
3 Correct 74 ms 3920 KB Correct.
4 Correct 67 ms 3920 KB Correct.
5 Correct 49 ms 3676 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2908 KB Correct.
2 Correct 18 ms 3064 KB Correct.
3 Correct 17 ms 2904 KB Correct.
4 Correct 18 ms 4188 KB Correct.
5 Correct 16 ms 2652 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3032 KB Correct.
2 Correct 15 ms 2908 KB Correct.
3 Correct 31 ms 9908 KB Correct.
4 Correct 13 ms 4000 KB Correct.
5 Correct 17 ms 2868 KB Correct.
6 Correct 17 ms 2908 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2984 KB Correct.
2 Correct 13 ms 3160 KB Correct.
3 Correct 242 ms 14464 KB Correct.
4 Correct 162 ms 7412 KB Correct.
5 Correct 282 ms 12776 KB Correct.
6 Correct 108 ms 11040 KB Correct.
7 Correct 166 ms 7368 KB Correct.
8 Correct 134 ms 5204 KB Correct.
9 Correct 57 ms 3952 KB Correct.
10 Correct 58 ms 3952 KB Correct.
11 Correct 123 ms 4832 KB Correct.
12 Correct 66 ms 3924 KB Correct.
13 Correct 64 ms 4028 KB Correct.
14 Correct 164 ms 9392 KB Correct.
15 Correct 156 ms 6232 KB Correct.
16 Correct 63 ms 3920 KB Correct.
17 Correct 74 ms 4124 KB Correct.
18 Correct 65 ms 3924 KB Correct.
19 Correct 187 ms 5016 KB Correct.
20 Correct 5 ms 2908 KB Correct.
21 Correct 6 ms 2908 KB Correct.
22 Correct 9 ms 3672 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 3064 KB Correct.
2 Correct 28 ms 3160 KB Correct.
3 Correct 259 ms 17156 KB Correct.
4 Correct 198 ms 5796 KB Correct.
5 Correct 897 ms 12956 KB Correct.
6 Correct 291 ms 10732 KB Correct.
7 Correct 384 ms 9552 KB Correct.
8 Correct 183 ms 5428 KB Correct.
9 Correct 140 ms 4048 KB Correct.
10 Correct 115 ms 3920 KB Correct.
11 Correct 156 ms 4088 KB Correct.
12 Correct 153 ms 4048 KB Correct.
13 Correct 148 ms 3968 KB Correct.
14 Correct 889 ms 11556 KB Correct.
15 Correct 652 ms 9720 KB Correct.
16 Correct 278 ms 7180 KB Correct.
17 Correct 196 ms 5240 KB Correct.
18 Correct 131 ms 4000 KB Correct.
19 Correct 171 ms 4068 KB Correct.
20 Correct 145 ms 3924 KB Correct.
21 Correct 460 ms 4944 KB Correct.
22 Correct 11 ms 2908 KB Correct.
23 Correct 11 ms 2908 KB Correct.
24 Correct 21 ms 3676 KB Correct.