oj.uz

Submission #1001951

# Submission time Handle Problem Language Result Execution time Memory
1001951 2024-06-19T08:44:24 Z underwaterkillerwhale Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 397256 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 = 1e15;
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][65];
    bool canGo[N];

    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, min(K, 63)) dp[i][k] = INF;
        BFS();
        priority_queue<Data, vector<Data>, cmp> pq;
        rep (i, 1, n) {
            if (i == 1 || (a[i] == 0 && canGo[i] == 1)) {
                rep (k, 0, min(K, 63)) {
                    dp[i][k] = 0;
                    pq.push({i, k, 0});
                }
            }
        }
        while (!pq.empty()) {
            int u = pq.top().u, k = pq.top().k;
            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 / (1LL << k)) {
                        dp[v][k] = dp[u][k] + 1.0 * w / (1LL << k);
                        if (v != H) pq.push({v, k, dp[v][k]});
                    }
                }
                else if (a[v] == 2) {
                    if (dp[v][k] > dp[u][k] + 1.0 * w / (1LL << k)) {
                        dp[v][k] = dp[u][k] + 1.0 * w / (1LL << k);
                        if (v != H) pq.push({v, k, dp[v][k]});
                    }
                    if (k >= 1 && dp[v][k - 1] > dp[u][k] + 1.0 * w / (1LL << k)) {
                        dp[v][k - 1] = dp[u][k] + 1.0 * w / (1LL << k);
                        if (v != H) pq.push({v, k - 1, dp[v][k - 1]});
                    }
                }
            }
        }
        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;
    ++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 27 ms 3164 KB Correct.
2 Correct 28 ms 3348 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 4180 KB Correct.
2 Correct 142 ms 4432 KB Correct.
3 Correct 136 ms 4436 KB Correct.
4 Correct 145 ms 4348 KB Correct.
5 Correct 137 ms 4432 KB Correct.
6 Correct 122 ms 9508 KB Correct.
7 Correct 165 ms 9564 KB Correct.
8 Correct 82 ms 14684 KB Correct.
9 Correct 119 ms 3668 KB Correct.
10 Correct 118 ms 3680 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 5148 KB Correct.
2 Correct 199 ms 4988 KB Correct.
3 Correct 194 ms 5116 KB Correct.
4 Correct 141 ms 3740 KB Correct.
5 Correct 148 ms 3664 KB Correct.
6 Correct 51 ms 10704 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 43972 KB Correct.
2 Correct 121 ms 4884 KB Correct.
3 Correct 110 ms 4896 KB Correct.
4 Correct 108 ms 4976 KB Correct.
5 Correct 86 ms 3668 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4436 KB Correct.
2 Correct 85 ms 4432 KB Correct.
3 Correct 84 ms 4432 KB Correct.
4 Correct 94 ms 9736 KB Correct.
5 Correct 68 ms 3548 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 5104 KB Correct.
2 Correct 93 ms 4984 KB Correct.
3 Correct 43 ms 48684 KB Correct.
4 Correct 87 ms 12532 KB Correct.
5 Correct 86 ms 3748 KB Correct.
6 Correct 104 ms 5108 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 5108 KB Correct.
2 Correct 26 ms 4696 KB Correct.
3 Correct 394 ms 61200 KB Correct.
4 Correct 237 ms 18124 KB Correct.
5 Correct 621 ms 52100 KB Correct.
6 Correct 320 ms 25796 KB Correct.
7 Correct 247 ms 18816 KB Correct.
8 Correct 209 ms 6952 KB Correct.
9 Correct 115 ms 4940 KB Correct.
10 Correct 115 ms 4928 KB Correct.
11 Correct 193 ms 5444 KB Correct.
12 Correct 126 ms 5084 KB Correct.
13 Correct 108 ms 4980 KB Correct.
14 Correct 215 ms 32080 KB Correct.
15 Correct 233 ms 12152 KB Correct.
16 Correct 115 ms 5044 KB Correct.
17 Correct 133 ms 5044 KB Correct.
18 Correct 129 ms 5076 KB Correct.
19 Correct 325 ms 6040 KB Correct.
20 Correct 10 ms 3164 KB Correct.
21 Correct 10 ms 3768 KB Correct.
22 Correct 22 ms 5328 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 397256 KB Time limit exceeded
2 Halted 0 ms 0 KB -