oj.uz

Submission #787643

# Submission time Handle Problem Language Result Execution time Memory
787643 2023-07-19T10:38:38 Z aymanrs Cyberland (APIO23_cyberland) C++17
0 / 100
 33 ms 12348 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);
        }
    }
    cout << ans << '\n';
}
// int main(){
//     cout << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << '\n';
// }

Compilation message

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
   43 | }
      | ^

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 12348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 668 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 632 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -