Submission #832750

#	Time	Username	Problem	Language	Result	Execution time	Memory
832750		jlallas384	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	0 ms	212 KiB

crocodile

#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);
                }
            }
        }
    }
}

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11