Submission #603101

#	Time	Username	Problem	Language	Result	Execution time	Memory
603101		JakobZorz	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	2 ms	596 KiB

crocodile

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <stack>
#include <math.h>
#include "crocodile.h"

#define MAX 1000000001

struct Conn {
    int dest;
    int weight;
};

struct Node {
    std::vector<Conn> connections;
    int optimal_time = -1;
    int getOptimalTime();
};

Node* nodes;

int Node::getOptimalTime() {
    if(optimal_time != -1)
        return optimal_time;
    
    int best_time = MAX, second_best_time = MAX;
    optimal_time = MAX + 1;
    
    for(Conn& conn : connections) {
        int weight = nodes[conn.dest].getOptimalTime() + conn.weight;
        if(weight <= best_time) {
            second_best_time = best_time;
            best_time = weight;
        } else if(weight <= second_best_time)
            second_best_time = weight;
    }
    
    optimal_time = second_best_time;
    return optimal_time;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    nodes = new Node[N];
    
    for(int i = 0; i < M; i++) {
        int a1 = R[i][0], a2 = R[i][1];
        Conn conn;
        conn.weight = L[i];
        
        conn.dest = a2;
        nodes[a1].connections.push_back(conn);
        
        conn.dest = a1;
        nodes[a2].connections.push_back(conn);
    }
    
    for(int i = 0; i < K; i++)
        nodes[P[i]].optimal_time = 0;
    
    int result = nodes[0].getOptimalTime();
    delete[] nodes;
    return result;
}

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