oj.uz

Submission #874719

# Submission time Handle Problem Language Result Execution time Memory
874719 2023-11-17T16:41:14 Z Itamar Cyberland (APIO23_cyberland) C++17
100 / 100
 2671 ms 74036 KB 
#include <vector>
using namespace std;
#define vi vector<int>
#define pi pair<int,int>
#define x first
#define y second
#include "cyberland.h"
#define pd pair<double,double>
#define pdi pair<double,int>
#define vd vector<double>
#include <vector>
#include <queue>

void dfs(vector<bool>&vis, int i, int H,vector<vector<pdi>>&fr) {
    if (i ==H)return;
    if (vis[i])return;
    vis[i] = 1;
    for (pdi p : fr[i]) {
        dfs(vis, p.y, H, fr);
    }
}

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) {
    K = min(K, 69);
    vector<vd> dp(N, vd(K + 2,1e15));
    vector<vector<pdi>> fr(N);
    for (int i = 0; i < M; i++) {
        fr[X[i]].push_back({ c[i],Y[i] });
        fr[Y[i]].push_back({ c[i],X[i] });
    }
    priority_queue<pair<int,pdi>> pq;
    vi fre;
    vector<bool> vis(N);
    dfs(vis, 0,H,fr);
    pq.push({ 0,{0,0} });
    for (int i = 0; i < N; i++)if (vis[i] == 1 && arr[i] == 0)pq.push({ 0,{0,i} });

    while (!pq.empty()) {
        pair<int, pdi> q = pq.top();
        int s = q.x;
        pdi p = q.y;
        pq.pop();
        if ((- s) > K)continue;
        if (dp[p.y][-s] < -p.x)continue;
        dp[p.y][-s] = -p.x;
        if (p.y == H)continue;
        for (pd f : fr[p.y]) {
            if(arr[p.y]==2)pq.push({ s - 1,{p.x / 2 - f.x,f.y} });
            if(f.x-p.x <= dp[f.y][-s])pq.push({ s,{p.x - f.x,f.y} });
        }
    }
    double mini = 1e15;
    for (int i = 0; i <= K; i++)mini = min(mini, dp[H][i]);
    if(mini==1e15)return -1;
    return mini;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 604 KB Correct.
2 Correct 18 ms 600 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 856 KB Correct.
2 Correct 27 ms 860 KB Correct.
3 Correct 26 ms 872 KB Correct.
4 Correct 29 ms 856 KB Correct.
5 Correct 26 ms 848 KB Correct.
6 Correct 23 ms 4256 KB Correct.
7 Correct 30 ms 4256 KB Correct.
8 Correct 14 ms 8280 KB Correct.
9 Correct 25 ms 344 KB Correct.
10 Correct 28 ms 552 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 856 KB Correct.
2 Correct 29 ms 900 KB Correct.
3 Correct 29 ms 920 KB Correct.
4 Correct 29 ms 348 KB Correct.
5 Correct 28 ms 344 KB Correct.
6 Correct 7 ms 3932 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 24348 KB Correct.
2 Correct 199 ms 924 KB Correct.
3 Correct 178 ms 940 KB Correct.
4 Correct 187 ms 860 KB Correct.
5 Correct 121 ms 544 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 856 KB Correct.
2 Correct 33 ms 856 KB Correct.
3 Correct 26 ms 860 KB Correct.
4 Correct 26 ms 4268 KB Correct.
5 Correct 23 ms 348 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 860 KB Correct.
2 Correct 25 ms 860 KB Correct.
3 Correct 46 ms 30544 KB Correct.
4 Correct 18 ms 3252 KB Correct.
5 Correct 29 ms 344 KB Correct.
6 Correct 26 ms 1112 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 912 KB Correct.
2 Correct 50 ms 856 KB Correct.
3 Correct 674 ms 28256 KB Correct.
4 Correct 298 ms 7420 KB Correct.
5 Correct 1179 ms 21964 KB Correct.
6 Correct 880 ms 17852 KB Correct.
7 Correct 297 ms 7736 KB Correct.
8 Correct 258 ms 1460 KB Correct.
9 Correct 263 ms 852 KB Correct.
10 Correct 253 ms 1128 KB Correct.
11 Correct 253 ms 940 KB Correct.
12 Correct 266 ms 852 KB Correct.
13 Correct 286 ms 936 KB Correct.
14 Correct 294 ms 10756 KB Correct.
15 Correct 281 ms 2912 KB Correct.
16 Correct 275 ms 852 KB Correct.
17 Correct 307 ms 964 KB Correct.
18 Correct 304 ms 908 KB Correct.
19 Correct 626 ms 860 KB Correct.
20 Correct 17 ms 348 KB Correct.
21 Correct 18 ms 752 KB Correct.
22 Correct 75 ms 2140 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 1248 KB Correct.
2 Correct 105 ms 1368 KB Correct.
3 Correct 800 ms 74036 KB Correct.
4 Correct 349 ms 3156 KB Correct.
5 Correct 2671 ms 33356 KB Correct.
6 Correct 2033 ms 20996 KB Correct.
7 Correct 627 ms 15172 KB Correct.
8 Correct 382 ms 3220 KB Correct.
9 Correct 569 ms 2124 KB Correct.
10 Correct 547 ms 2132 KB Correct.
11 Correct 194 ms 1620 KB Correct.
12 Correct 573 ms 2116 KB Correct.
13 Correct 624 ms 2420 KB Correct.
14 Correct 1858 ms 32076 KB Correct.
15 Correct 1154 ms 36856 KB Correct.
16 Correct 528 ms 13848 KB Correct.
17 Correct 410 ms 4688 KB Correct.
18 Correct 596 ms 2384 KB Correct.
19 Correct 665 ms 2224 KB Correct.
20 Correct 655 ms 2288 KB Correct.
21 Correct 1360 ms 3244 KB Correct.
22 Correct 33 ms 604 KB Correct.
23 Correct 39 ms 1096 KB Correct.
24 Correct 168 ms 2492 KB Correct.