Submission #1307635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307635		3lektra	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	2 ms	2616 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]});
        dis[P[i]].first = dis[P[i]].second = 0;
    }

    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 + u.first > 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]});
    }
    
    int inf = -1e9;
    dis = vector<pair<int,int>>(N,{inf,0});  
        
    dijkstra(K,P);

    return -fpath;
}

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