oj.uz

답안 #603103

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603103 2022-07-23T15:32:00 Z JakobZorz 악어의 지하 도시 (IOI11_crocodile) C++14
46 / 100
 2 ms 596 KB 
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <stack>
#include <math.h>

#define MAX 1000000001

struct Conn {
    long long dest;
    long long weight;
};

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

Node* nodes;

long long Node::getOptimalTime() {
    if(optimal_time != -1)
        return optimal_time;
    
    long long best_time = MAX, second_best_time = MAX;
    optimal_time = MAX + 1;
    
    for(Conn& conn : connections) {
        long long 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(long long i = 0; i < M; i++) {
        long long 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(long long 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -