Submission #832754

# Submission time Handle Problem Language Result Execution time Memory
832754 2023-08-21T14:31:16 Z jlallas384 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
0 ms 212 KB
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using ll = long long;
struct edge{
    int u, v, w;
    int oth(int o){
        return u ^ v ^ o;
    }
};

int travel_plan(int n, int m, int r[][2], int L[], int k, int p[]){
    vector<int> lst(n);
    for(int i = 0; i < k; i++){
        lst[p[i]] = 1;
    }
    vector<edge> edges;
    vector<vector<int>> g(n);
    vector<int> deg(n);
    for(int i = 0; i < m; i++){
        edges.push_back({r[i][0], r[i][1], L[i]});
        g[r[i][0]].push_back(i);
        g[r[i][1]].push_back(i);
        deg[r[i][0]]++;
        deg[r[i][1]]++;
    }
    vector<int> eban(m), ban(n, -1), proc(n);
    while(true){
        vector<ll> dist(n, 1e18), par(n);
        dist[0] = 0;
        priority_queue<pair<ll,int>> pq;
        pq.emplace(0, 0);
        while(pq.size()){
            auto [d, v] = pq.top(); pq.pop();
            if(-d > dist[v]) continue;
            if(lst[v]){
                int has = 0;
                while(v != 0){
                    int u = edges[par[v]].oth(v);
                    if(ban[u] == -1){
                        has = 1;
                        ban[u] = par[v];
                        eban[par[v]] = 1;
                    }
                    v = u;
                }
                if(!has) return -d;
                else break;
            }
            for(int e: g[v]) if(!eban[e]){
                int u = edges[e].oth(v);
                if(dist[u] >= dist[v] + edges[e].w){
                    dist[u] = dist[v] + edges[e].w;
                    par[u] = e;
                    pq.emplace(-dist[u], u);
                }
            }
        }
    }
}





# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -