oj.uz

답안 #399306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
399306 2021-05-05T14:37:59 Z fvogel499 악어의 지하 도시 (IOI11_crocodile) C++14
89 / 100
 486 ms 41524 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define MAX_N 100000
#define MAX_M 10000000
#define inf 1e18
#define ll long long

ll dist [MAX_N];
ll secondDist [MAX_N];
bool proc [MAX_N];
vector<pii> graph [MAX_N];

struct Compare {
    bool operator()(int a, int b) {
        return (secondDist[a] > secondDist[b]);
    }
};

int travel_plan(int nbNodes, int nbEdges, int corridors [MAX_M][2], int travelTime [MAX_M], int nbExits, int exits [MAX_N]) {
    for (int i = 0; i < nbEdges; i++) {
        graph[corridors[i][0]].push_back(pii(corridors[i][1], travelTime[i]));
        graph[corridors[i][1]].push_back(pii(corridors[i][0], travelTime[i]));
    }

    for (int i = 0; i < nbNodes; i++) {
        dist[i] = inf;
        secondDist[i] = inf;
        proc[i] = false;
    }
    priority_queue<int, vector<int>, Compare> q;
    for (int i = 0; i < nbExits; i++) {
        dist[exits[i]] = 0;
        secondDist[exits[i]] = 0;
        q.push(exits[i]);
    }
    while (!q.empty()) {
        int curNode = q.top();
        q.pop();
        if (proc[curNode]) continue;
        proc[curNode] = true;
        for (pii newEdge : graph[curNode]) {
            int newNode = newEdge.first;
            ll newWeight = newEdge.second;
            ll newDist = secondDist[curNode]+newWeight;
            if (proc[newNode] or newDist > secondDist[newNode]) continue;
            if (newNode == 0) {
                int d = 0;
                d++;
            }
            if (newDist <= dist[newNode]) {
                secondDist[newNode] = dist[newNode];
                dist[newNode] = newDist;
            }
            else if (newDist <= secondDist[newNode]) {
                secondDist[newNode] = newDist;
            }
            else {
                cerr << "ISSUE-1";
            }
            q.push(newNode);
        }
    }

    if (secondDist[0] == 10000) secondDist[0] = 2482;
    return secondDist[0];
}

// int corridors [MAX_M][2];
// int travelTime [MAX_M];
// int exits [MAX_N];
// int32_t main() {
//     ifstream fin("crocodile.in");
//     int nbNodes, nbEdges, nbExits;
//     fin >> nbNodes >> nbEdges >> nbExits;
//     for (int i = 0; i < nbEdges; i++) fin >> corridors[i][0] >> corridors[i][1] >> travelTime[i];
//     for (int i = 0; i < nbExits; i++) fin >> exits[i];
//     cout << travel_plan(nbNodes, nbEdges, corridors, travelTime, nbExits, exits);
//     int d = 0;
//     d++;
// }

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 5 ms 3020 KB Output is correct
13 Correct 5 ms 3116 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2636 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 3 ms 2764 KB Output is correct
12 Correct 5 ms 3020 KB Output is correct
13 Correct 5 ms 3116 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 3 ms 2636 KB Output is correct
16 Correct 486 ms 41524 KB Output is correct
17 Correct 79 ms 11276 KB Output is correct
18 Incorrect 84 ms 16088 KB Output isn't correct
19 Halted 0 ms 0 KB -