답안 #363220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
363220	2021-02-05T09:58:03 Z	Pety	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	853 ms	67444 KB

crocodile

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

vector<pii>G[100002];
int viz[100002];
int dist[100002], dist2[100002];

int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]) {
  for (int i = 0; i < k; i++) {
    if (!p[i])
      return 0;
  }
  for (int i = 0; i < m; i++) {
    G[r[i][0]].push_back({r[i][1], l[i]});
    G[r[i][1]].push_back({r[i][0], l[i]});
  }
  queue<int>q;
  priority_queue<pii, vector<pii>, greater<pii> >pq;
  for (int i = 0; i < n; i++)
    dist[i] = 1e9;
  for (int i = 0; i < k; i++) {
    dist[p[i]] = 0;
    viz[p[i]] = 1;
    pq.push({0, p[i]});
  }
  while (pq.size()) {
    int nod =  pq.top().second;
    int aux = pq.top().first;
    pq.pop();
    if (viz[nod] == 2)
      continue;
    if (viz[nod] == 0) {
      viz[nod] = 1;
      continue;
    }
    if (viz[nod] == 1)
      viz[nod] = 2;
    dist[nod] = aux;
    for (auto it : G[nod]) {
      if (viz[it.first] < 2)
        pq.push({dist[nod] + it.second, it.first});

    }
  }
  return dist[0];
}

Subtask #1

46.0 / 46.0

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

Subtask #2

43.0 / 43.0

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

Subtask #3

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2816 KB	Output is correct
2	Correct	2 ms	2668 KB	Output is correct
3	Correct	2 ms	2668 KB	Output is correct
4	Correct	3 ms	2796 KB	Output is correct
5	Correct	3 ms	2796 KB	Output is correct
6	Correct	3 ms	2796 KB	Output is correct
7	Correct	3 ms	2796 KB	Output is correct
8	Correct	3 ms	2796 KB	Output is correct
9	Correct	6 ms	3052 KB	Output is correct
10	Correct	2 ms	2668 KB	Output is correct
11	Correct	3 ms	2796 KB	Output is correct
12	Correct	12 ms	3436 KB	Output is correct
13	Correct	13 ms	3436 KB	Output is correct
14	Correct	3 ms	2668 KB	Output is correct
15	Correct	4 ms	2796 KB	Output is correct
16	Correct	776 ms	64552 KB	Output is correct
17	Correct	83 ms	13804 KB	Output is correct
18	Correct	115 ms	15340 KB	Output is correct
19	Correct	853 ms	67444 KB	Output is correct
20	Correct	499 ms	57944 KB	Output is correct
21	Correct	45 ms	7788 KB	Output is correct
22	Correct	466 ms	46540 KB	Output is correct