Submission #787646

#	Time	Username	Problem	Language	Result	Execution time	Memory
787646		aymanrs	Cyberland (APIO23_cyberland)	C++17	44 / 100	32 ms	9200 KiB

cyberland

#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 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3