Submission #1010716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010716		a_aguilo	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	424 ms	77420 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
//#include "crocodile.h"
#define vi vector<int>
#define vc vector
#define pi pair<int,int>
using namespace std;

vc<vc<pi>> edg; // Edges, aka the corridors coming out from each room
vi padreSecond;
vi padreFirst;
vc<pi> dis; // The two minimum distances found between 2 nodes. The fastest route will just be used to calculate the second fastest, which is the oke that will be used to obtain the other distances
int fpath = -1e9-7; // Fastest path
int u, c; // Amazing the amount of situations when a node and a cost can be useful

void dijkstra(int k, int p[]){
    priority_queue<vi> tv; // To Visit, not TeleVision or To Vandalize
    for(int i = 0; i < k; i++){
        tv.push({0,p[i], -1});
        dis[p[i]].first = 0;
        dis[p[i]].second = 0;
      }
    while(!tv.empty()){
        vector<int> act = tv.top();
        u = act[1]; // The node being explored right now
        c = act[0];
        int padre = act[2]; // The cost to get to u
        tv.pop();
        
        if((dis[u].second!=c) or (padre != padreSecond[u])){continue;} // If this path is worse then why bother
        if(u == 0){
            fpath = max(fpath, c);
            continue;}
            
        for(pi p : edg[u]){     // p.first = cost, p.second = node the path leads to
          if(p.second != u and dis[p.second].first != 0){
            if (p.first + c > dis[p.second].second){    // If this is path you've found is fastest than the second fastest one...
                if (p.first + c > dis[p.second].first){     // And than the fastest one...
                    dis[p.second].second = dis[p.second].first;     // Then the previously fastest one becomes the second fastest one...
                    padreSecond[p.second] = padreFirst[p.second];
                    padreFirst[p.second] = u;
                    dis[p.second].first = p.first + c;}     // This new path becomes the fastest!
                    
                else{ // But if it's not fastest than the fastest one...
                    dis[p.second].second = p.first + c;
                    padreSecond[p.second] = u;
                  }
                    
                tv.push({dis[p.second].second, p.second, padreSecond[p.second]});
            

            }
          }
        }
    }
}



int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  padreSecond = vi(N, -1);
  padreFirst = vi(N, -1);
    edg = vc<vc<pi>>(N);
    for(int i = 0; i < M; i++){
        edg[R[i][0]].push_back({-L[i],R[i][1]});
        edg[R[i][1]].push_back({-L[i],R[i][0]});}
    
    dis = vc<pi>(N,{-1e9-7,-1e9-7});  
        
    dijkstra(K,P);

return -fpath;}

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