Submission #1307625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307625		3lektra	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	1887 ms	327680 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;

const int maxN = 1e5;

vector<pair<int, int>> dis; 
vector<pair<int, int>> graph[maxN];
int par[maxN]; // i know this is not technically the parent, but
int fpath;

void dijkstra(int k, int P[]){
    priority_queue<pair<int,int>> tv;
    for(int i = 0; i < k; ++i) tv.push({0, P[i]}); 

    while(!tv.empty()){
        int node = tv.top().second;
        int d = tv.top().first;
        tv.pop();

        if(d < dis[node].second) continue;
        if(node = 0){
            fpath = max(fpath, d);
            continue;
        }

        for(pair<int,int> u : graph[node]){
            if(d > dis[node].second && u.second != par[node]){
                if(d + u.first > dis[node].first){
                    dis[u.second].second = dis[node].first;
                    dis[u.second].first = d + u.first;
                    par[u.second] = node;
                }
                else{
                    dis[u.second].second = d + u.first;
                }

                tv.push({d + u.first, u.second});

            }
        }

    }

}




int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    memset(graph, 0, sizeof(graph));
    for(int i = 0; i < M; i++){
        graph[R[i][0]].push_back({-L[i],R[i][1]});
        graph[R[i][1]].push_back({-L[i],R[i][0]});}
    
    dis = vector<pair<int,int>>(N,{-1e9-7,-1e9-7});  
        
    dijkstra(K,P);

    return -fpath;
}


/*
int main(){
    int n, m, k;
    int u, v, c;
    cin >> n >> m >> k;
    for(int i = m; i < m; ++i){
        cin >> u >> v >> c;
        u--; v--;
        graph[u].push_back({-c, v});
        graph[v].push_back({-c, u});
    }

}
*/

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