oj.uz

Submission #946314

# Submission time Handle Problem Language Result Execution time Memory
946314 2024-03-14T13:41:49 Z Nhoksocqt1 Cyberland (APIO23_cyberland) C++17
97 / 100
 400 ms 54876 KB 
#ifndef Nhoksocqt1
    #include "cyberland.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<double, int> pdi;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

vector<ii> adj[MAXN];
double dist[31][MAXN];
int cityType[MAXN], numNode, numType0, cyberCity;

double solve(int _N, int _M, int _K, int _H, vector<int> _X, vector<int> _Y, vector<int> _C, vector<int> _A) {
    numNode = _N, numType0 = _K, cyberCity = _H;
    for (int i = 0; i < numNode; ++i)
        adj[i].clear();

    for (int i = 0; i < _M; ++i) {
        int u(_X[i]), v(_Y[i]), w(_C[i]);
        adj[u].push_back(ii(v, w));
        adj[v].push_back(ii(u, w));
    }

    for (int i = 0; i < numNode; ++i)
        cityType[i] = _A[i];

    for (int j = 0; j <= numType0; ++j) {
        for (int i = 0; i < numNode; ++i)
            dist[j][i] = 1e18;
    }

    dist[0][0] = 0;
    for (int k = 0; k <= numType0; ++k) {
        priority_queue<pdi, vector<pdi>, greater<pdi>> heap;
        for (int i = 0; i < numNode; ++i) {
            if(dist[k][i] < ll(1e18))
                heap.push({dist[k][i], i});
        }

        while(sz(heap)) {
            double dis(heap.top().fi);
            int u(heap.top().se);
            heap.pop();

            if(u == cyberCity || dis != dist[k][u])
                continue;

            for (int it = 0; it < sz(adj[u]); ++it) {
                int v(adj[u][it].fi), w(adj[u][it].se);
                if(cityType[v] > 0) {
                    if(dist[k][v] > dist[k][u] + w) {
                        dist[k][v] = dist[k][u] + w;
                        heap.push({dist[k][v], v});
                    }

                    if(cityType[v] == 2 && k < numType0)
                        dist[k + 1][v] = min(dist[k + 1][v], (dist[k][u] + w) / 2.0);
                } else
                    if(dist[k][v] > 0) {
                        dist[k][v] = 0;
                        heap.push({dist[k][v], v});
                    }
            }
        }
    }

    double res(1e18);
    for (int k = 0; k <= numType0; ++k)
        res = min(res, dist[k][cyberCity]);

    return (res >= 1e18) ? -1 : res;
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "cyberland"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> _X, _Y, _C, _A;
    int _N, _M, _K, _H;
    cin >> _N >> _M >> _K >> _H;

    _X.resize(_M);
    _Y.resize(_M);
    _C.resize(_M);
    for (int i = 0; i < _M; ++i)
        cin >> _X[i] >> _Y[i] >> _C[i];

    _A.resize(_N);
    for (int i = 0; i < _N; ++i)
        cin >> _A[i];

    double ans = solve(_N, _M, _K, _H, _X, _Y, _C, _A);
    cout << setprecision(6) << fixed;
    cout << "ANSWER: " << ans << '\n';

    return 0;
}

#endif // Nhoksocqt1

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27224 KB Correct.
2 Correct 20 ms 27740 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27456 KB Correct.
2 Correct 24 ms 27392 KB Correct.
3 Correct 23 ms 27228 KB Correct.
4 Correct 24 ms 27228 KB Correct.
5 Correct 24 ms 27420 KB Correct.
6 Correct 21 ms 27992 KB Correct.
7 Correct 27 ms 27996 KB Correct.
8 Correct 16 ms 28764 KB Correct.
9 Correct 23 ms 27228 KB Correct.
10 Correct 23 ms 27228 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 27228 KB Correct.
2 Correct 25 ms 27368 KB Correct.
3 Correct 24 ms 27436 KB Correct.
4 Correct 25 ms 27148 KB Correct.
5 Correct 28 ms 27484 KB Correct.
6 Correct 8 ms 27740 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 31296 KB Correct.
2 Correct 87 ms 27404 KB Correct.
3 Correct 88 ms 27392 KB Correct.
4 Correct 85 ms 27356 KB Correct.
5 Correct 64 ms 27224 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27484 KB Correct.
2 Correct 24 ms 28508 KB Correct.
3 Correct 24 ms 28252 KB Correct.
4 Correct 23 ms 29136 KB Correct.
5 Correct 21 ms 27996 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27480 KB Correct.
2 Correct 21 ms 28252 KB Correct.
3 Correct 40 ms 34236 KB Correct.
4 Correct 17 ms 28508 KB Correct.
5 Correct 35 ms 28248 KB Correct.
6 Correct 30 ms 28252 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 27472 KB Correct.
2 Correct 19 ms 27484 KB Correct.
3 Correct 400 ms 28332 KB Correct.
4 Correct 260 ms 29148 KB Correct.
5 Correct 335 ms 34620 KB Correct.
6 Correct 166 ms 33192 KB Correct.
7 Correct 256 ms 31096 KB Correct.
8 Correct 206 ms 29584 KB Correct.
9 Correct 78 ms 28200 KB Correct.
10 Correct 80 ms 28460 KB Correct.
11 Correct 175 ms 29368 KB Correct.
12 Correct 91 ms 28292 KB Correct.
13 Correct 90 ms 28596 KB Correct.
14 Correct 234 ms 32480 KB Correct.
15 Correct 235 ms 30152 KB Correct.
16 Correct 85 ms 28484 KB Correct.
17 Correct 109 ms 28500 KB Correct.
18 Correct 96 ms 28428 KB Correct.
19 Correct 294 ms 29296 KB Correct.
20 Correct 8 ms 27228 KB Correct.
21 Correct 10 ms 27228 KB Correct.
22 Correct 18 ms 27740 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 54876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -