oj.uz

Submission #874709

# Submission time Handle Problem Language Result Execution time Memory
874709 2023-11-17T16:34:13 Z Itamar Cyberland (APIO23_cyberland) C++17
97 / 100
 1765 ms 59936 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, 50);
    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()) {
        int s = pq.top().x;
        pdi p = pq.top().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} });
            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 19 ms 520 KB Correct.
2 Correct 23 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 860 KB Correct.
2 Correct 32 ms 860 KB Correct.
3 Correct 30 ms 860 KB Correct.
4 Correct 31 ms 860 KB Correct.
5 Correct 31 ms 860 KB Correct.
6 Correct 28 ms 4252 KB Correct.
7 Correct 37 ms 4252 KB Correct.
8 Correct 20 ms 8292 KB Correct.
9 Correct 28 ms 344 KB Correct.
10 Correct 27 ms 348 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 860 KB Correct.
2 Correct 37 ms 860 KB Correct.
3 Correct 34 ms 856 KB Correct.
4 Correct 32 ms 348 KB Correct.
5 Correct 31 ms 576 KB Correct.
6 Correct 8 ms 4128 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 24656 KB Correct.
2 Correct 290 ms 1096 KB Correct.
3 Correct 257 ms 964 KB Correct.
4 Correct 271 ms 868 KB Correct.
5 Correct 183 ms 592 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 912 KB Correct.
2 Correct 29 ms 824 KB Correct.
3 Correct 29 ms 868 KB Correct.
4 Correct 31 ms 4192 KB Correct.
5 Correct 24 ms 360 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 932 KB Correct.
2 Correct 30 ms 860 KB Correct.
3 Correct 45 ms 30604 KB Correct.
4 Correct 21 ms 3512 KB Correct.
5 Correct 28 ms 600 KB Correct.
6 Correct 29 ms 860 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 920 KB Correct.
2 Correct 73 ms 856 KB Correct.
3 Correct 1076 ms 28488 KB Correct.
4 Correct 535 ms 7296 KB Correct.
5 Correct 1765 ms 25180 KB Correct.
6 Correct 1375 ms 16844 KB Correct.
7 Correct 544 ms 7644 KB Correct.
8 Correct 452 ms 1584 KB Correct.
9 Correct 393 ms 996 KB Correct.
10 Correct 387 ms 1168 KB Correct.
11 Correct 431 ms 1172 KB Correct.
12 Correct 398 ms 1072 KB Correct.
13 Correct 425 ms 932 KB Correct.
14 Correct 509 ms 11104 KB Correct.
15 Correct 502 ms 2948 KB Correct.
16 Correct 412 ms 840 KB Correct.
17 Correct 457 ms 1056 KB Correct.
18 Correct 455 ms 944 KB Correct.
19 Correct 905 ms 860 KB Correct.
20 Correct 25 ms 512 KB Correct.
21 Correct 29 ms 604 KB Correct.
22 Correct 119 ms 2136 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 1408 KB Correct.
2 Correct 119 ms 1116 KB Correct.
3 Incorrect 767 ms 59936 KB Wrong Answer.
4 Halted 0 ms 0 KB -