oj.uz

Submission #787646

# Submission time Handle Problem Language Result Execution time Memory
787646 2023-07-19T10:39:27 Z aymanrs Cyberland (APIO23_cyberland) C++17
44 / 100
 32 ms 9200 KB 
#include <bits/stdc++.h>
using namespace std;

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){
    vector<pair<int, int>> g[N];
    for(int i = 0;i < M;i++){
        g[x[i]].emplace_back(y[i], c[i]);
        g[y[i]].emplace_back(x[i], c[i]);
    }
    long long d[N];
    fill(d, d+N, LONG_LONG_MAX);
    d[H] = 0;
    set<pair<long long, int>> s;
    s.insert(make_pair(0, H));
    while(!s.empty()){
        auto p = *s.begin();
        s.erase(s.begin());
        for(auto [c, co] : g[p.second]){
            if(p.first + co < d[c]){
                auto f = s.find(make_pair(d[c], c));
                if(f != s.end()) s.erase(f);
                d[c] = p.first+co;
                s.insert(make_pair(d[c], c));
            }
        }
    }
    if(d[0] == LONG_LONG_MAX) return -1;
    long long ans = d[0];
    queue<int> q;
    q.push(0);
    bool v[N] = {false};
    v[0] = v[H] = true;
    while(!q.empty()){
        int t = q.front();
        q.pop();
        if(!arr[t]) ans = min(ans, d[t]);
        for(auto [c, co] : g[t]) if(!v[c]) {
            v[c] = true;
            q.push(c);
        }
    }
    return ans;
}
// int main(){
//     cout << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << '\n';
// }

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 468 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 812 KB Correct.
2 Correct 26 ms 1148 KB Correct.
3 Correct 25 ms 1236 KB Correct.
4 Correct 25 ms 1208 KB Correct.
5 Correct 27 ms 1180 KB Correct.
6 Correct 21 ms 2092 KB Correct.
7 Correct 28 ms 2004 KB Correct.
8 Correct 12 ms 2760 KB Correct.
9 Correct 22 ms 1032 KB Correct.
10 Correct 22 ms 1084 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1100 KB Correct.
2 Correct 24 ms 1260 KB Correct.
3 Correct 23 ms 1236 KB Correct.
4 Correct 23 ms 616 KB Correct.
5 Correct 23 ms 1164 KB Correct.
6 Correct 5 ms 1240 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 5700 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1164 KB Correct.
2 Correct 24 ms 1256 KB Correct.
3 Correct 23 ms 1252 KB Correct.
4 Correct 22 ms 2120 KB Correct.
5 Correct 19 ms 980 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1092 KB Correct.
2 Correct 20 ms 1124 KB Correct.
3 Correct 32 ms 9200 KB Correct.
4 Correct 14 ms 1620 KB Correct.
5 Correct 23 ms 1208 KB Correct.
6 Correct 23 ms 1116 KB Correct.

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 1236 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 980 KB Wrong Answer.
2 Halted 0 ms 0 KB -