oj.uz

Submission #410341

# Submission time Handle Problem Language Result Execution time Memory
410341 2021-05-22T14:21:27 Z 600Mihnea Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1938 ms 74060 KB 
#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;

const int N = 100000 + 7;
const int INF = (int) 1e9 + 7;
int n, m, k, best[N];
vector<pair<int, int>> lol[N];
vector<pair<int, int>> g[N];
priority_queue<pair<int, int>> q;

int lt[N], step;

void push(int i, int value) {

  for (auto &it : g[i]) {
    lol[it.first].push_back({min(INF, value + it.second), i});
    sort(lol[it.first].begin(), lol[it.first].end());
    step++;
    vector<pair<int, int>> lol2;
    for (auto &k : lol[it.first]) {
      if (lt[k.second] != step) {
        lol2.push_back(k);
        lt[k.second] = step;
        if ((int) lol2.size() == 2) {
          break;
        }
      }
    }
    lol[it.first] = lol2;
  }
  best[i] = value;
  q.push({-best[i], i});
}

int get_second(int a) {
  if ((int) lol[a].size() < 2) {
    return INF;
  }
  return lol[a][1].first;
}

int travel_plan(int nn, int mm, int r[][2], int len[], int kk, int ch[]) {
  n = nn;
  m = mm;
  k = kk;
  for (int i = 0; i < n; i++) {
    g[i].clear();
    lol[i].clear();
    best[i] = INF;
  }
  for (int i = 0; i < m; i++) {
    g[r[i][0]].push_back({r[i][1], len[i]});
    g[r[i][1]].push_back({r[i][0], len[i]});
    lol[r[i][0]].push_back({INF, r[i][1]});
    lol[r[i][1]].push_back({INF, r[i][0]});
  }
  for (int i = 0; i < k; i++) {
    push(ch[i], 0);
  }
  while (!q.empty()) {
    int a = q.top().second, o = -q.top().first;
    q.pop();
    if (best[a] != o) {
      continue;
    }
    for (auto &it : g[a]) {
      int node = it.first, relax = get_second(node);
      if (relax < best[node]) {
        push(node, relax);
      }
    }
  }
  if (best[0] == INF) {
    best[0] = -1;
  }
  return best[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 7 ms 5360 KB Output is correct
10 Correct 4 ms 5048 KB Output is correct
11 Correct 5 ms 5160 KB Output is correct
12 Correct 13 ms 5536 KB Output is correct
13 Correct 10 ms 5708 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5068 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 7 ms 5360 KB Output is correct
10 Correct 4 ms 5048 KB Output is correct
11 Correct 5 ms 5160 KB Output is correct
12 Correct 13 ms 5536 KB Output is correct
13 Correct 10 ms 5708 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5068 KB Output is correct
16 Correct 1649 ms 68188 KB Output is correct
17 Correct 149 ms 25284 KB Output is correct
18 Correct 205 ms 25460 KB Output is correct
19 Correct 1938 ms 74060 KB Output is correct
20 Correct 774 ms 61864 KB Output is correct
21 Correct 75 ms 12560 KB Output is correct
22 Correct 685 ms 55112 KB Output is correct