oj.uz

Submission #1052431

# Submission time Handle Problem Language Result Execution time Memory
1052431 2024-08-10T14:30:15 Z SN0WM4N Cyberland (APIO23_cyberland) C++17
100 / 100
 1245 ms 87892 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sort undefined_function // To use stable_sort instead sort 
#define bpc __builtin_popcount
#define ull unsigned long long
#define ld double
#define ll long long
#define mp make_pair
#define F first
#define S second

#pragma GCC optimize("O3")

#ifdef LOCAL 
        #include "debug.h"
#else 
        #define dbg(...) 0
        #include <cyberland.h>
#endif

using namespace __gnu_pbds;
using namespace std;

typedef tree<long long, null_type, less_equal<long long>,
    rb_tree_tag, tree_order_statistics_node_update> Tree;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
const ll MOD = 998244353; //[998244353, 1e9 + 7, 1e9 + 13]
const ld PI = acos(-1);
const ll NROOT = 800;

ll binpow(ll a, ll b, ll _MOD = -1) {
        if (_MOD == -1)
                _MOD = MOD;
        ll res = 1;
        for (; b; b /= 2, a *= a, a %= _MOD)
                if (b & 1) res *= a, res %= _MOD;
        return res;
}

void set_IO(string s) {
#ifndef LOCAL
        string in  = s +  ".in";
        string out = s + ".out";
        freopen(in.c_str(),  "r",  stdin);
        freopen(out.c_str(), "w", stdout);
#endif
}

bool dataOverflow(ll a, ll b) {return (log10(a) + log10(b) >= 18);}
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll ceil(ll a, ll b) {return (a + b - 1) / b;}
ll invmod(ll a) {return binpow(a, MOD - 2);}

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
        vector<vector<pair<int, ld>>> g(N);
        for (int i = 0; i < M; i ++) {
                g[x[i]].push_back({y[i], c[i]});
                g[y[i]].push_back({x[i], c[i]});
        }

        K = min(K, 90);

        vector<double> power(K + 1);
        power[0] = 1.0;
        for (int i = 1; i <= K; i ++) 
                power[i] = power[i - 1] * 0.5;

        vector<vector<ld>> dis(N, vector<ld> (K + 1, 1e18));
        using T = pair<ld, pair<int, int>>;
        priority_queue<T, vector<T>, greater<T>> q;

        dis[0][0] = 0;
        q.push({0, {0, 0}});

        queue<int> Q;
        Q.push(0);
        vector<int> vis(N);

        while (!Q.empty()) {
                int node = Q.front();
                Q.pop();

                if (vis[node])
                        continue;
                vis[node] = 1;
                if (node == H)
                        continue;

                if (arr[node] == 0) {
                        q.push({0, {0, node}});
                        dis[node][0] = 0;
                }

                for (auto &[to, _] : g[node]) 
                        Q.push(to);
        }

        if (!vis[H])
                return -1;
        
        double ans = 1e18;

        for (int iter = 0; iter <= K; iter ++) {
                priority_queue<T, vector<T>, greater<T>> tmp;

                while (!q.empty()) {
                        ld d = q.top().F;
                        auto [used, node] = q.top().S;
                        q.pop();

                        if (node == H)
                                continue;
                        if (dis[node][used] < d)
                                continue;

                        for (auto &[to, w] : g[node]) {
                                if (dis[to][used] > d + (1.0 * w)) {
                                        q.push({d + (1.0 * w), {used, to}});
                                        dis[to][used] = d + (1.0 * w);
                                }

                                if (used > K)
                                        continue;

                                if (arr[node] == 2 && dis[to][used + 1] > (d * 0.5 + (1.0 * w))) {
                                        tmp.push({d * 0.5 + (1.0 * w), {used + 1, to}});
                                        dis[to][used + 1] = (d * 0.5) + (1.0 * w);
                                }
                        }
                }

                swap(tmp, q);
        }

        for (auto &val : dis[H])
                ans = min(ans, val);

        return ans;
}

Compilation message

cyberland.cpp: In function 'void set_IO(std::string)':
cyberland.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(in.c_str(),  "r",  stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cyberland.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(out.c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 856 KB Correct.
2 Correct 13 ms 856 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1624 KB Correct.
2 Correct 19 ms 1712 KB Correct.
3 Correct 21 ms 1724 KB Correct.
4 Correct 18 ms 1884 KB Correct.
5 Correct 19 ms 1884 KB Correct.
6 Correct 17 ms 5024 KB Correct.
7 Correct 22 ms 5336 KB Correct.
8 Correct 13 ms 8284 KB Correct.
9 Correct 17 ms 1368 KB Correct.
10 Correct 17 ms 1452 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1624 KB Correct.
2 Correct 20 ms 1716 KB Correct.
3 Correct 22 ms 1672 KB Correct.
4 Correct 22 ms 1372 KB Correct.
5 Correct 19 ms 1372 KB Correct.
6 Correct 5 ms 3676 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 24324 KB Correct.
2 Correct 71 ms 1756 KB Correct.
3 Correct 62 ms 1796 KB Correct.
4 Correct 66 ms 1772 KB Correct.
5 Correct 42 ms 1308 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1756 KB Correct.
2 Correct 23 ms 1756 KB Correct.
3 Correct 18 ms 1984 KB Correct.
4 Correct 17 ms 4956 KB Correct.
5 Correct 15 ms 1368 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1884 KB Correct.
2 Correct 15 ms 1660 KB Correct.
3 Correct 33 ms 31580 KB Correct.
4 Correct 12 ms 3496 KB Correct.
5 Correct 16 ms 1448 KB Correct.
6 Correct 17 ms 1828 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1812 KB Correct.
2 Correct 14 ms 1112 KB Correct.
3 Correct 341 ms 30628 KB Correct.
4 Correct 213 ms 9416 KB Correct.
5 Correct 380 ms 21424 KB Correct.
6 Correct 169 ms 11872 KB Correct.
7 Correct 205 ms 8424 KB Correct.
8 Correct 149 ms 3036 KB Correct.
9 Correct 62 ms 1804 KB Correct.
10 Correct 56 ms 1612 KB Correct.
11 Correct 126 ms 2640 KB Correct.
12 Correct 73 ms 1780 KB Correct.
13 Correct 73 ms 1872 KB Correct.
14 Correct 203 ms 11272 KB Correct.
15 Correct 189 ms 4696 KB Correct.
16 Correct 66 ms 1808 KB Correct.
17 Correct 80 ms 1868 KB Correct.
18 Correct 70 ms 1812 KB Correct.
19 Correct 209 ms 2768 KB Correct.
20 Correct 4 ms 604 KB Correct.
21 Correct 5 ms 604 KB Correct.
22 Correct 13 ms 1648 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 2224 KB Correct.
2 Correct 29 ms 1880 KB Correct.
3 Correct 222 ms 87892 KB Correct.
4 Correct 231 ms 5368 KB Correct.
5 Correct 1132 ms 38140 KB Correct.
6 Correct 482 ms 16940 KB Correct.
7 Correct 495 ms 17648 KB Correct.
8 Correct 178 ms 3308 KB Correct.
9 Correct 121 ms 2216 KB Correct.
10 Correct 105 ms 2160 KB Correct.
11 Correct 118 ms 1732 KB Correct.
12 Correct 137 ms 2276 KB Correct.
13 Correct 138 ms 2376 KB Correct.
14 Correct 1245 ms 36788 KB Correct.
15 Correct 911 ms 44404 KB Correct.
16 Correct 345 ms 13504 KB Correct.
17 Correct 214 ms 5196 KB Correct.
18 Correct 124 ms 2292 KB Correct.
19 Correct 159 ms 2544 KB Correct.
20 Correct 134 ms 2552 KB Correct.
21 Correct 394 ms 3152 KB Correct.
22 Correct 7 ms 604 KB Correct.
23 Correct 9 ms 1284 KB Correct.
24 Correct 30 ms 1880 KB Correct.