oj.uz

Submission #749682

# Submission time Handle Problem Language Result Execution time Memory
749682 2023-05-28T11:24:15 Z Sacharlemagne Cyberland (APIO23_cyberland) C++17
100 / 100
 1888 ms 75480 KB 
#include "cyberland.h"
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const double INF = 1e18;
ll h,k;

vector<int> zeroes;
typedef priority_queue<pair<double,pll>, vector<pair<double,pll> >, greater<> > pita;
pita other;
void dijkstra(vector<vector<double> > &dist, vector<vector<pll>> &adj, vi &arr) {
    vector<bool> visited(dist.size());
    pita pq;
    swap(pq,other);
    while (!pq.empty()) {
        double curDist = pq.top().first;
        pll p = pq.top().second;
        pq.pop();
        ll K = p.second, node = p.first;
        if (node == h) continue;
        if (visited[node]) continue;
        visited[node] = true;
        for (pll u : adj[p.first]) {
            if (dist[u.first][K] > (curDist+u.second)) {
                dist[u.first][K] = curDist+u.second;
                pq.push({curDist+u.second,{u.first,K}});
            }
            if (arr[u.first] == 2 && K < k) {
                if (dist[u.first][K+1] > (curDist+u.second)/2.) {
                    dist[u.first][K+1] = (curDist+u.second)/2.;
                    other.push({(curDist+u.second)/2.,{u.first,K+1}});
                }
            }
        }
    }
}

void dfs(int node, vector<bool> &visited, vector<vector<pll> > &adj, vi &arr) {
    if (visited[node]) return;
    visited[node] = true;
    if (arr[node] == 0) zeroes.push_back(node);
    for (pll u : adj[node]) {
        dfs(u.first,visited,adj,arr);
    }
}

double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
    K=min(K,69);
    zeroes.clear();
    other = pita();
    other.push({0,{0,0}});

    h = H, k = K;
    vector<vector<pll> > adj(N);
    for (int i = 0; i<M; ++i) {
        adj[x[i]].push_back({y[i],c[i]});
        adj[y[i]].push_back({x[i],c[i]});
    }
    vector<bool> visited(N, false);
    visited[H] = true;
    dfs(0,visited,adj,arr);
    for (int i : zeroes) {
        adj[0].push_back({i,0});
    }
    vector<vector<double> > dist(N,vector<double>(k+1,INF));
    dist[0][0] = 0;
    for (int i = 0; i<=K; ++i) {
        dijkstra(dist,adj,arr);
    }
    double res = *min_element(dist[h].begin(),dist[h].end());
    return res==INF?-1:res;
}

/**
* 1
3 3 69 2
1 2 1
0 1 1
0 2 2
1 2 1


 1
3 2 2
2
1 2 1
0 1 3
1 2 2

5 4 69 4
1 1 0 1 1
0 1 10
0 2 2
2 3 1
2 4 1

 6 5 69 1
1 1 0 1 0 1
0 1 2
1 2 1
1 3 5
3 4 69
3 5 2

 3 4 60 1
 1 1 1
0 1 6
0 2 2
2 1 3
0 2 4

 8 8 69 6
1 1 1 0 1 1 1 0
0 1 1
0 2 1
1 4 1
2 3 1
2 5 1
4 6 1
5 6 1
6 7 1

 6 5 5 5
 1 0 2 2 2 1
0 1 4
1 2 8
2 3 8
3 4 8
4 5 0

 10
3 2 30 2
1 2 1
1 2 12
2 0 4
 4 4 30 3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 348 KB Correct.
2 Correct 30 ms 464 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 724 KB Correct.
2 Correct 36 ms 720 KB Correct.
3 Correct 29 ms 692 KB Correct.
4 Correct 31 ms 704 KB Correct.
5 Correct 31 ms 708 KB Correct.
6 Correct 26 ms 4128 KB Correct.
7 Correct 38 ms 4004 KB Correct.
8 Correct 18 ms 7908 KB Correct.
9 Correct 35 ms 468 KB Correct.
10 Correct 32 ms 428 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 712 KB Correct.
2 Correct 35 ms 736 KB Correct.
3 Correct 30 ms 792 KB Correct.
4 Correct 41 ms 424 KB Correct.
5 Correct 34 ms 400 KB Correct.
6 Correct 10 ms 3700 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 23804 KB Correct.
2 Correct 131 ms 784 KB Correct.
3 Correct 123 ms 792 KB Correct.
4 Correct 128 ms 808 KB Correct.
5 Correct 86 ms 524 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 720 KB Correct.
2 Correct 29 ms 724 KB Correct.
3 Correct 30 ms 720 KB Correct.
4 Correct 27 ms 3972 KB Correct.
5 Correct 27 ms 340 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 756 KB Correct.
2 Correct 25 ms 724 KB Correct.
3 Correct 69 ms 29420 KB Correct.
4 Correct 18 ms 3028 KB Correct.
5 Correct 29 ms 416 KB Correct.
6 Correct 29 ms 720 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 720 KB Correct.
2 Correct 22 ms 852 KB Correct.
3 Correct 842 ms 28588 KB Correct.
4 Correct 358 ms 7208 KB Correct.
5 Correct 776 ms 21356 KB Correct.
6 Correct 261 ms 10708 KB Correct.
7 Correct 353 ms 7264 KB Correct.
8 Correct 283 ms 1624 KB Correct.
9 Correct 128 ms 752 KB Correct.
10 Correct 123 ms 720 KB Correct.
11 Correct 240 ms 796 KB Correct.
12 Correct 140 ms 740 KB Correct.
13 Correct 150 ms 772 KB Correct.
14 Correct 396 ms 10048 KB Correct.
15 Correct 276 ms 2748 KB Correct.
16 Correct 145 ms 720 KB Correct.
17 Correct 166 ms 744 KB Correct.
18 Correct 151 ms 824 KB Correct.
19 Correct 386 ms 756 KB Correct.
20 Correct 9 ms 340 KB Correct.
21 Correct 11 ms 608 KB Correct.
22 Correct 19 ms 1336 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 952 KB Correct.
2 Correct 43 ms 1364 KB Correct.
3 Correct 941 ms 75480 KB Correct.
4 Correct 346 ms 3012 KB Correct.
5 Correct 1763 ms 32432 KB Correct.
6 Correct 639 ms 14180 KB Correct.
7 Correct 660 ms 13936 KB Correct.
8 Correct 338 ms 1396 KB Correct.
9 Correct 239 ms 1060 KB Correct.
10 Correct 247 ms 1040 KB Correct.
11 Correct 271 ms 640 KB Correct.
12 Correct 264 ms 1064 KB Correct.
13 Correct 265 ms 1028 KB Correct.
14 Correct 1888 ms 30780 KB Correct.
15 Correct 1538 ms 34768 KB Correct.
16 Correct 548 ms 12200 KB Correct.
17 Correct 352 ms 2876 KB Correct.
18 Correct 268 ms 1092 KB Correct.
19 Correct 328 ms 1072 KB Correct.
20 Correct 309 ms 1012 KB Correct.
21 Correct 836 ms 1064 KB Correct.
22 Correct 15 ms 340 KB Correct.
23 Correct 19 ms 896 KB Correct.
24 Correct 37 ms 1672 KB Correct.