oj.uz

Submission #1002103

# Submission time Handle Problem Language Result Execution time Memory
1002103 2024-06-19T09:56:31 Z underwaterkillerwhale Cyberland (APIO23_cyberland) C++17
100 / 100
 963 ms 64084 KB 
#ifdef ONLINE_JUDGE
    #include "cyberland.h"
#endif

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 1e5 + 7;
const int Mod = 1e9 +7;
const int szBL = 50;
const ll INF = 1e18;
const int BASE = 137;

struct toEdge {
    int v, w;
};

int n, m, K, H;
int a[N];
vector<toEdge> ke[N];

namespace sub1 {
    double dist[N];

    double solution() {
        rep (i, 1, n) dist[i] = INF;
        priority_queue<pair<double, int>, vector<pair<double,int>>, greater<pair<double, int>> > Q; Q.push({0, 1});
        dist[1] = 0;
        while (!Q.empty()) {
            int u = Q.top().se;
            Q.pop();
            iter (&id, ke[u]) {
                int v = id.v, w = id.w;
                double delta = dist[u] + w;
                if (a[v] == 2) delta /= 2.0;
                else if (a[v] == 0) delta = 0;
                if (dist[v] > delta) {
                    dist[v] = delta;
                    if (v != H) {
                        Q.push({dist[v], v});
                    }
                }
            }
        }
        if (dist[H] == INF) return -1;
        else return dist[H];
    }
}

namespace sub160907 {
    struct Data {
            ll u, k;
            double val;
    };
    struct cmp {
        bool operator () (Data A, Data B) { return A.val > B.val; }
    };

    double dp[N][70];
    bool canGo[N];
    double PW[70];

    void BFS () {
        rep (i, 1, n) canGo[i] = 0;
        queue<int> Q;
        Q.push(1);
        canGo[1] = 1;
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            iter (&id, ke[u]) {
                if (!canGo[id.v]) {
                    canGo[id.v] = 1;
                    if (id.v != H) Q.push(id.v);
                }
            }
        }
    }

    double solution() {
        rep (i, 1, n) rep (k, 0, K) dp[i][k] = INF;
        PW[0] = 1;
        rep (i, 1, K) PW[i] = PW[i - 1] / 2;
        BFS();
        reb (k, K, 0) {
            priority_queue<pair<double,int>, vector<pair<double,int>>, greater<pair<double,int>> > pq;
            rep (i, 1, n) {
                if (i == 1 || (a[i] == 0 && canGo[i] == 1)) {
                    dp[i][k] = 0;
                }
                if (dp[i][k] != INF) pq.push({dp[i][k], i});
            }
            while (!pq.empty()) {
                int u = pq.top().se;
                pq.pop();
                iter (&id, ke[u]) {
                    ll v = id.v, w = id.w;
                    if (a[v] == 0) continue;
                    if (a[v] == 1) {
                        if (dp[v][k] > dp[u][k] + 1.0 * w * PW[k]) {
                            dp[v][k] = dp[u][k] + 1.0 * w * PW[k];
                            if (v != H) pq.push({dp[v][k], v});
                        }
                    }
                    else if (a[v] == 2) {
                        if (dp[v][k] > dp[u][k] + 1.0 * w * PW[k]) {
                            dp[v][k] = dp[u][k] + 1.0 * w * PW[k];
                            if (v != H) pq.push({dp[v][k], v});
                        }
                        if (k >= 1 && dp[v][k - 1] > dp[u][k] + 1.0 * w * PW[k]) {
                            dp[v][k - 1] = dp[u][k] + 1.0 * w * PW[k];
                        }
                    }
                }
            }
        }
        if (dp[H][0] != INF) return dp[H][0];
        return -1;
    }
}

double solve (int _n, int _m, int _K, int _H, vector<int> _U, vector<int> _V, vector<int> _W, vector<int> _A) {
    n = _n;
    m = _m;
    K = _K;
    H = _H;
    K = min(K, 67);
    ++H;
    rep (i ,1, n) ke[i].clear();
    rep (i, 1, n) {
        a[i] = _A[i - 1];
    }
    rep (i, 0, m - 1) {
        int u = _U[i], v = _V[i], w = _W[i];
        ++u, ++v;
        ke[u].push_back({v, w});
        ke[v].push_back({u, w});
    }
//    if (n <= 3 && K <= 30)
//        return sub1 :: solution();
//    else
        return sub160907 :: solution();
}

//void solution() {
//    cin >> n >> m >> K >> H;
//    ++H;
//    rep (i, 1, n) cin >> a[i];
//    rep (i, 1, m) {
//        int u, v, w;
//        cin >> u >> v>> w;
//        ++u, ++v;
//        ke[u].push_back({v, w});
//        ke[v].push_back({u, w});
//    }
//    cout << sub1 :: solution () <<"\n";
//    cout << sub160907 :: solution () <<"\n";
//}
//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
//int main () {
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
////    file ("c");
//    int num_Test = 1;
//    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}

/*
1
3 2 30
2
1 2 1
1 2 12
2 0 4

1
4 4 30
3
1 1 2 1
0 1 5
0 2 5
1 3 2
2 3 4


3 2
0 1 5
0 2 5
1
1 2

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3164 KB Correct.
2 Correct 21 ms 3160 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4180 KB Correct.
2 Correct 75 ms 4436 KB Correct.
3 Correct 66 ms 4480 KB Correct.
4 Correct 61 ms 4436 KB Correct.
5 Correct 61 ms 4436 KB Correct.
6 Correct 140 ms 9552 KB Correct.
7 Correct 187 ms 9424 KB Correct.
8 Correct 93 ms 15452 KB Correct.
9 Correct 46 ms 3440 KB Correct.
10 Correct 49 ms 3548 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 4184 KB Correct.
2 Correct 72 ms 4176 KB Correct.
3 Correct 65 ms 4168 KB Correct.
4 Correct 53 ms 3668 KB Correct.
5 Correct 50 ms 3664 KB Correct.
6 Correct 39 ms 8200 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 40204 KB Correct.
2 Correct 67 ms 4180 KB Correct.
3 Correct 56 ms 4176 KB Correct.
4 Correct 56 ms 4172 KB Correct.
5 Correct 40 ms 3420 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4276 KB Correct.
2 Correct 44 ms 4184 KB Correct.
3 Correct 54 ms 4180 KB Correct.
4 Correct 106 ms 9656 KB Correct.
5 Correct 27 ms 3676 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4180 KB Correct.
2 Correct 36 ms 4152 KB Correct.
3 Correct 54 ms 51056 KB Correct.
4 Correct 59 ms 7768 KB Correct.
5 Correct 34 ms 3668 KB Correct.
6 Correct 45 ms 4176 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4180 KB Correct.
2 Correct 13 ms 3932 KB Correct.
3 Correct 377 ms 63492 KB Correct.
4 Correct 255 ms 17472 KB Correct.
5 Correct 366 ms 29156 KB Correct.
6 Correct 186 ms 13852 KB Correct.
7 Correct 246 ms 18772 KB Correct.
8 Correct 187 ms 6228 KB Correct.
9 Correct 62 ms 4188 KB Correct.
10 Correct 67 ms 4108 KB Correct.
11 Correct 138 ms 5028 KB Correct.
12 Correct 65 ms 4180 KB Correct.
13 Correct 63 ms 4300 KB Correct.
14 Correct 241 ms 33036 KB Correct.
15 Correct 188 ms 11860 KB Correct.
16 Correct 70 ms 3416 KB Correct.
17 Correct 65 ms 3528 KB Correct.
18 Correct 70 ms 3416 KB Correct.
19 Correct 191 ms 3480 KB Correct.
20 Correct 5 ms 2648 KB Correct.
21 Correct 6 ms 3420 KB Correct.
22 Correct 14 ms 3676 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 3420 KB Correct.
2 Correct 20 ms 3932 KB Correct.
3 Correct 207 ms 64084 KB Correct.
4 Correct 207 ms 8908 KB Correct.
5 Correct 653 ms 29728 KB Correct.
6 Correct 337 ms 14352 KB Correct.
7 Correct 413 ms 27500 KB Correct.
8 Correct 157 ms 5652 KB Correct.
9 Correct 83 ms 4432 KB Correct.
10 Correct 93 ms 4340 KB Correct.
11 Correct 118 ms 3940 KB Correct.
12 Correct 103 ms 4340 KB Correct.
13 Correct 94 ms 4436 KB Correct.
14 Correct 963 ms 30044 KB Correct.
15 Correct 660 ms 35576 KB Correct.
16 Correct 347 ms 15864 KB Correct.
17 Correct 195 ms 6992 KB Correct.
18 Correct 84 ms 4436 KB Correct.
19 Correct 114 ms 4384 KB Correct.
20 Correct 108 ms 4516 KB Correct.
21 Correct 291 ms 5356 KB Correct.
22 Correct 7 ms 2908 KB Correct.
23 Correct 9 ms 3420 KB Correct.
24 Correct 26 ms 3932 KB Correct.