oj.uz

Submission #603101

# Submission time Handle Problem Language Result Execution time Memory
603101 2022-07-23T15:29:53 Z JakobZorz Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 2 ms 596 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Incorrect 0 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Incorrect 0 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -