oj.uz

Submission #874715

# Submission time Handle Problem Language Result Execution time Memory
874715 2023-11-17T16:38:48 Z Itamar Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 74132 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} });
            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 604 KB Correct.
2 Correct 19 ms 600 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 856 KB Correct.
2 Correct 32 ms 872 KB Correct.
3 Correct 34 ms 852 KB Correct.
4 Correct 32 ms 664 KB Correct.
5 Correct 31 ms 860 KB Correct.
6 Correct 35 ms 4768 KB Correct.
7 Correct 37 ms 4252 KB Correct.
8 Correct 18 ms 8284 KB Correct.
9 Correct 29 ms 564 KB Correct.
10 Correct 30 ms 552 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 848 KB Correct.
2 Correct 33 ms 860 KB Correct.
3 Correct 31 ms 928 KB Correct.
4 Correct 32 ms 348 KB Correct.
5 Correct 31 ms 344 KB Correct.
6 Correct 8 ms 4124 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 24908 KB Correct.
2 Correct 306 ms 868 KB Correct.
3 Correct 254 ms 948 KB Correct.
4 Correct 276 ms 856 KB Correct.
5 Correct 180 ms 544 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 856 KB Correct.
2 Correct 29 ms 1112 KB Correct.
3 Correct 29 ms 860 KB Correct.
4 Correct 30 ms 4288 KB Correct.
5 Correct 26 ms 556 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 856 KB Correct.
2 Correct 27 ms 860 KB Correct.
3 Correct 45 ms 30600 KB Correct.
4 Correct 22 ms 3508 KB Correct.
5 Correct 30 ms 556 KB Correct.
6 Correct 30 ms 856 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 1060 KB Correct.
2 Correct 73 ms 856 KB Correct.
3 Correct 1055 ms 28424 KB Correct.
4 Correct 552 ms 7188 KB Correct.
5 Correct 1852 ms 25540 KB Correct.
6 Correct 1392 ms 16576 KB Correct.
7 Correct 538 ms 7592 KB Correct.
8 Correct 457 ms 1684 KB Correct.
9 Correct 394 ms 848 KB Correct.
10 Correct 381 ms 1076 KB Correct.
11 Correct 435 ms 960 KB Correct.
12 Correct 395 ms 1048 KB Correct.
13 Correct 449 ms 996 KB Correct.
14 Correct 509 ms 10992 KB Correct.
15 Correct 486 ms 3172 KB Correct.
16 Correct 415 ms 1088 KB Correct.
17 Correct 471 ms 964 KB Correct.
18 Correct 475 ms 844 KB Correct.
19 Correct 905 ms 916 KB Correct.
20 Correct 25 ms 348 KB Correct.
21 Correct 27 ms 748 KB Correct.
22 Correct 122 ms 2120 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1055 ms 1184 KB Correct.
2 Correct 163 ms 1372 KB Correct.
3 Correct 1125 ms 74132 KB Correct.
4 Correct 635 ms 3152 KB Correct.
5 Execution timed out 3021 ms 37396 KB Time limit exceeded
6 Halted 0 ms 0 KB -