oj.uz

Submission #1001956

# Submission time Handle Problem Language Result Execution time Memory
1001956 2024-06-19T08:46:52 Z underwaterkillerwhale Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 397272 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});
                }
            }
        }
        ll res = INF;
        while (!pq.empty()) {
            int u = pq.top().u, k = pq.top().k;
            if (u == H && k == 0) {
                if (res == INF)
                    res = dp[u][k];
                else assert(res <= dp[u][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 26 ms 3164 KB Correct.
2 Correct 27 ms 3164 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 4328 KB Correct.
2 Correct 141 ms 4300 KB Correct.
3 Correct 127 ms 4320 KB Correct.
4 Correct 139 ms 4432 KB Correct.
5 Correct 153 ms 4308 KB Correct.
6 Correct 148 ms 9496 KB Correct.
7 Correct 185 ms 9532 KB Correct.
8 Correct 84 ms 14680 KB Correct.
9 Correct 109 ms 3800 KB Correct.
10 Correct 113 ms 3664 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 5088 KB Correct.
2 Correct 199 ms 5044 KB Correct.
3 Correct 186 ms 5104 KB Correct.
4 Correct 148 ms 3664 KB Correct.
5 Correct 143 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 44020 KB Correct.
2 Correct 127 ms 5028 KB Correct.
3 Correct 102 ms 5032 KB Correct.
4 Correct 127 ms 4888 KB Correct.
5 Correct 90 ms 3856 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4432 KB Correct.
2 Correct 82 ms 4412 KB Correct.
3 Correct 94 ms 4576 KB Correct.
4 Correct 103 ms 9604 KB Correct.
5 Correct 69 ms 3664 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 5060 KB Correct.
2 Correct 96 ms 4976 KB Correct.
3 Correct 42 ms 48476 KB Correct.
4 Correct 86 ms 12616 KB Correct.
5 Correct 87 ms 3868 KB Correct.
6 Correct 106 ms 5120 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 5060 KB Correct.
2 Correct 22 ms 4740 KB Correct.
3 Correct 368 ms 61276 KB Correct.
4 Correct 240 ms 18200 KB Correct.
5 Correct 552 ms 52232 KB Correct.
6 Correct 325 ms 25792 KB Correct.
7 Correct 243 ms 18776 KB Correct.
8 Correct 204 ms 6960 KB Correct.
9 Correct 111 ms 4964 KB Correct.
10 Correct 115 ms 5044 KB Correct.
11 Correct 201 ms 5444 KB Correct.
12 Correct 119 ms 4992 KB Correct.
13 Correct 138 ms 5144 KB Correct.
14 Correct 224 ms 32040 KB Correct.
15 Correct 209 ms 12512 KB Correct.
16 Correct 136 ms 5096 KB Correct.
17 Correct 141 ms 5128 KB Correct.
18 Correct 136 ms 5056 KB Correct.
19 Correct 369 ms 5988 KB Correct.
20 Correct 10 ms 2908 KB Correct.
21 Correct 10 ms 3768 KB Correct.
22 Correct 28 ms 5332 KB Correct.

Subtask #8
0.0 / 3.0

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