oj.uz

Submission #1001967

# Submission time Handle Problem Language Result Execution time Memory
1001967 2024-06-19T08:52:06 Z underwaterkillerwhale Cyberland (APIO23_cyberland) C++17
97 / 100
 556 ms 62948 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, 61)) 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, 61)) {
                    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 / (1LL << k)) {
                        dp[v][k] = dp[u][k] + 1.0 * w / (1LL << 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 / (1LL << 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 / (1LL << k)) {
                        dp[v][k - 1] = dp[u][k] + 1.0 * w / (1LL << 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:107:12: warning: unused variable 'res' [-Wunused-variable]
  107 |         ll res = INF;
      |            ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3164 KB Correct.
2 Correct 28 ms 3096 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 4180 KB Correct.
2 Correct 144 ms 4444 KB Correct.
3 Correct 141 ms 4432 KB Correct.
4 Correct 136 ms 4452 KB Correct.
5 Correct 142 ms 4432 KB Correct.
6 Correct 131 ms 9596 KB Correct.
7 Correct 171 ms 9532 KB Correct.
8 Correct 84 ms 14816 KB Correct.
9 Correct 120 ms 3668 KB Correct.
10 Correct 119 ms 3668 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 5088 KB Correct.
2 Correct 214 ms 5116 KB Correct.
3 Correct 185 ms 5092 KB Correct.
4 Correct 150 ms 3668 KB Correct.
5 Correct 150 ms 3740 KB Correct.
6 Correct 50 ms 10704 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 43984 KB Correct.
2 Correct 126 ms 5028 KB Correct.
3 Correct 109 ms 5032 KB Correct.
4 Correct 118 ms 4884 KB Correct.
5 Correct 90 ms 3668 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4432 KB Correct.
2 Correct 89 ms 4592 KB Correct.
3 Correct 91 ms 4580 KB Correct.
4 Correct 104 ms 9740 KB Correct.
5 Correct 73 ms 3664 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 5144 KB Correct.
2 Correct 100 ms 4988 KB Correct.
3 Correct 42 ms 48464 KB Correct.
4 Correct 78 ms 12616 KB Correct.
5 Correct 81 ms 3668 KB Correct.
6 Correct 97 ms 5092 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 5044 KB Correct.
2 Correct 20 ms 4856 KB Correct.
3 Correct 54 ms 60912 KB Correct.
4 Correct 55 ms 18152 KB Correct.
5 Correct 556 ms 52156 KB Correct.
6 Correct 300 ms 25888 KB Correct.
7 Correct 42 ms 18952 KB Correct.
8 Correct 68 ms 6896 KB Correct.
9 Correct 119 ms 5072 KB Correct.
10 Correct 105 ms 4928 KB Correct.
11 Correct 54 ms 5440 KB Correct.
12 Correct 127 ms 5108 KB Correct.
13 Correct 122 ms 4984 KB Correct.
14 Correct 47 ms 31984 KB Correct.
15 Correct 42 ms 12364 KB Correct.
16 Correct 119 ms 5036 KB Correct.
17 Correct 136 ms 5012 KB Correct.
18 Correct 132 ms 5088 KB Correct.
19 Correct 341 ms 6044 KB Correct.
20 Correct 10 ms 2908 KB Correct.
21 Correct 10 ms 3768 KB Correct.
22 Correct 18 ms 5332 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 5688 KB Correct.
2 Correct 43 ms 5840 KB Correct.
3 Incorrect 196 ms 62948 KB Wrong Answer.
4 Halted 0 ms 0 KB -