oj.uz

Submission #1001979

# Submission time Handle Problem Language Result Execution time Memory
1001979 2024-06-19T08:57:06 Z underwaterkillerwhale Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 397356 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][67];
    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 power (double n, int m) {
        if (m == 0) return 1;
        double t = power (n, m >> 1);
        t *= t;
        if (m & 1) t *= n;
        return t;
    }

    double solution() {
        rep (i, 1, n) rep (k, 0, min(K, 65)) 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, 65)) {
                    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) {
                return 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 / power (2, k)) {
                        dp[v][k] = dp[u][k] + 1.0 * w / power (2, k);
                        if (v != H || k == 0) pq.push({v, k, dp[v][k]});
                    }
                }
                else if (a[v] == 2) {
                    if (dp[v][k] > dp[u][k] + 1.0 * w / power (2, k)) {
                        dp[v][k] = dp[u][k] + 1.0 * w / (1LL << k);
                        if (v != H || k == 0) pq.push({v, k, dp[v][k]});
                    }
                    if (k >= 1 && dp[v][k - 1] > dp[u][k] + 1.0 * w / power (2, k)) {
                        dp[v][k - 1] = dp[u][k] + 1.0 * w / power (2, k);
                        if (v != H || k == 0) pq.push({v, k - 1, dp[v][k - 1]});
                    }
                }
            }
        }
        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

*/

Compilation message

cyberland.cpp: In function 'double sub160907::solution()':
cyberland.cpp:115:12: warning: unused variable 'res' [-Wunused-variable]
  115 |         ll res = INF;
      |            ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3220 KB Correct.
2 Correct 30 ms 3080 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 4352 KB Correct.
2 Correct 156 ms 4448 KB Correct.
3 Correct 153 ms 4688 KB Correct.
4 Correct 146 ms 4436 KB Correct.
5 Correct 151 ms 4432 KB Correct.
6 Correct 141 ms 9516 KB Correct.
7 Correct 194 ms 9704 KB Correct.
8 Correct 89 ms 14940 KB Correct.
9 Correct 151 ms 3664 KB Correct.
10 Correct 143 ms 3668 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 5084 KB Correct.
2 Correct 208 ms 5084 KB Correct.
3 Correct 202 ms 5144 KB Correct.
4 Correct 173 ms 3872 KB Correct.
5 Correct 159 ms 3920 KB Correct.
6 Correct 50 ms 10804 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 44740 KB Correct.
2 Correct 158 ms 4936 KB Correct.
3 Correct 117 ms 5032 KB Correct.
4 Correct 123 ms 4856 KB Correct.
5 Correct 112 ms 3668 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 4436 KB Correct.
2 Correct 121 ms 4428 KB Correct.
3 Correct 116 ms 4604 KB Correct.
4 Correct 117 ms 9792 KB Correct.
5 Correct 109 ms 3668 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 4980 KB Correct.
2 Correct 140 ms 4960 KB Correct.
3 Correct 80 ms 49744 KB Correct.
4 Correct 115 ms 12608 KB Correct.
5 Correct 112 ms 3756 KB Correct.
6 Correct 127 ms 5072 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 4956 KB Correct.
2 Correct 38 ms 4696 KB Correct.
3 Correct 68 ms 62328 KB Correct.
4 Correct 46 ms 18464 KB Correct.
5 Correct 905 ms 52556 KB Correct.
6 Correct 341 ms 26048 KB Correct.
7 Correct 43 ms 19328 KB Correct.
8 Correct 47 ms 6904 KB Correct.
9 Correct 141 ms 5096 KB Correct.
10 Correct 136 ms 4944 KB Correct.
11 Correct 64 ms 5616 KB Correct.
12 Correct 172 ms 5192 KB Correct.
13 Correct 155 ms 4984 KB Correct.
14 Correct 45 ms 32700 KB Correct.
15 Correct 43 ms 12560 KB Correct.
16 Correct 156 ms 5012 KB Correct.
17 Correct 172 ms 5168 KB Correct.
18 Correct 172 ms 5084 KB Correct.
19 Correct 392 ms 6120 KB Correct.
20 Correct 14 ms 2908 KB Correct.
21 Correct 12 ms 3768 KB Correct.
22 Correct 28 ms 5504 KB Correct.

Subtask #8
0.0 / 3.0

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