답안 #851221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851221	2023-09-19T02:05:22 Z	NeroZein	악어의 지하 도시 (IOI11_crocodile)	C++17	89 / 100	420 ms	47336 KB

crocodile

#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std; 

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  vector<vector<pair<int, int>>> g(N);
  for (int i = 0; i < M; ++i) {
    g[R[i][0]].emplace_back(R[i][1], L[i]);
    g[R[i][1]].emplace_back(R[i][0], L[i]);
  }
  const int INF = 1e9; 
  vector<vector<int>> dis(N, vector<int> (2, INF)); 
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 
  for (int i = 0; i < K; ++i) {
    dis[P[i]][0] = dis[P[i]][1] = 0;
    pq.emplace(0, P[i]);
  }
  while (!pq.empty()) {
    auto [c, v] = pq.top();
    pq.pop();
    if (c != dis[v][1]) {
      continue;
    }
    for (auto [u, w] : g[v]) {
      int nc = c + w;
      if (nc < dis[u][1]) {
        dis[u][1] = nc; 
        if (dis[u][0] > dis[u][1]) {
          swap(dis[u][0], dis[u][1]); 
        }
        if (dis[u][1] != INF) {
          pq.emplace(dis[u][1], u); 
        }
      }
    }
  }
  return dis[0][1];
}

Subtask #1

46.0 / 46.0

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

Subtask #2

43.0 / 43.0

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

Subtask #3

0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4440 KB	Output is correct
3	Correct	1 ms	4440 KB	Output is correct
4	Correct	2 ms	4444 KB	Output is correct
5	Correct	2 ms	4440 KB	Output is correct
6	Correct	2 ms	4440 KB	Output is correct
7	Correct	2 ms	4440 KB	Output is correct
8	Correct	1 ms	4440 KB	Output is correct
9	Correct	2 ms	4696 KB	Output is correct
10	Correct	1 ms	4440 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	3 ms	4696 KB	Output is correct
13	Correct	3 ms	4696 KB	Output is correct
14	Correct	1 ms	4440 KB	Output is correct
15	Correct	1 ms	4440 KB	Output is correct
16	Correct	291 ms	40948 KB	Output is correct
17	Correct	56 ms	16976 KB	Output is correct
18	Correct	69 ms	17748 KB	Output is correct
19	Correct	420 ms	47336 KB	Output is correct
20	Correct	196 ms	34896 KB	Output is correct
21	Correct	28 ms	9164 KB	Output is correct
22	Incorrect	229 ms	33448 KB	Output isn't correct
23	Halted	0 ms	0 KB	-