oj.uz

Submission #192443

# Submission time Handle Problem Language Result Execution time Memory
192443 2020-01-15T06:07:59 Z kdh9949 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 801 ms 61480 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
#define x first
#define y second

static const int N = 100000;

int d[N][2], upd[N];
vector<pii> e[N];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
  for(int i = 0; i < m; i++){
    e[R[i][0]].emplace_back(R[i][1], L[i]);
    e[R[i][1]].emplace_back(R[i][0], L[i]);
  }
  
  memset(d, 0x3f, sizeof(d));
  for(int i = 0; i < k; i++){
    d[P[i]][0] = d[P[i]][1] = 0;
    pq.emplace(0, P[i]);
  }

  while(!pq.empty()){
    pii c = pq.top();
    pq.pop();
    if(c.x != d[c.y][1] || upd[c.y]) continue;
    upd[c.y] = 1;
    for(pii i : e[c.y]){
      if(d[i.x][1] > c.x + i.y){
        if(d[i.x][0] >= c.x + i.y){ d[i.x][1] = d[i.x][0]; d[i.x][0] = c.x + i.y; }
        else d[i.x][1] = c.x + i.y;
        pq.emplace(c.x + i.y, i.x);
      }
    }
  }

  return d[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 6 ms 3448 KB Output is correct
3 Correct 5 ms 3520 KB Output is correct
4 Correct 7 ms 3576 KB Output is correct
5 Correct 7 ms 3576 KB Output is correct
6 Correct 7 ms 3576 KB Output is correct
7 Correct 7 ms 3552 KB Output is correct
8 Correct 6 ms 3580 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 6 ms 3448 KB Output is correct
3 Correct 5 ms 3520 KB Output is correct
4 Correct 7 ms 3576 KB Output is correct
5 Correct 7 ms 3576 KB Output is correct
6 Correct 7 ms 3576 KB Output is correct
7 Correct 7 ms 3552 KB Output is correct
8 Correct 6 ms 3580 KB Output is correct
9 Correct 7 ms 3704 KB Output is correct
10 Correct 6 ms 3420 KB Output is correct
11 Correct 6 ms 3576 KB Output is correct
12 Correct 10 ms 3884 KB Output is correct
13 Correct 8 ms 3960 KB Output is correct
14 Correct 5 ms 3448 KB Output is correct
15 Correct 6 ms 3528 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 6 ms 3448 KB Output is correct
3 Correct 5 ms 3520 KB Output is correct
4 Correct 7 ms 3576 KB Output is correct
5 Correct 7 ms 3576 KB Output is correct
6 Correct 7 ms 3576 KB Output is correct
7 Correct 7 ms 3552 KB Output is correct
8 Correct 6 ms 3580 KB Output is correct
9 Correct 7 ms 3704 KB Output is correct
10 Correct 6 ms 3420 KB Output is correct
11 Correct 6 ms 3576 KB Output is correct
12 Correct 10 ms 3884 KB Output is correct
13 Correct 8 ms 3960 KB Output is correct
14 Correct 5 ms 3448 KB Output is correct
15 Correct 6 ms 3528 KB Output is correct
16 Correct 650 ms 58068 KB Output is correct
17 Correct 102 ms 14148 KB Output is correct
18 Correct 137 ms 15604 KB Output is correct
19 Correct 801 ms 61480 KB Output is correct
20 Correct 352 ms 50324 KB Output is correct
21 Correct 53 ms 8388 KB Output is correct
22 Correct 390 ms 46668 KB Output is correct