oj.uz

Submission #410336

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

using namespace std;

typedef long long ll;

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);
  }
  int cnt = 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];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:64:7: warning: unused variable 'cnt' [-Wunused-variable]
   64 |   int cnt = 0;
      |       ^~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 5068 KB Output is correct
6 Correct 4 ms 5040 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 4 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 5 ms 5068 KB Output is correct
6 Correct 4 ms 5040 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 5324 KB Output is correct
10 Correct 4 ms 4968 KB Output is correct
11 Correct 6 ms 5068 KB Output is correct
12 Correct 13 ms 5580 KB Output is correct
13 Correct 10 ms 5736 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 4 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 5 ms 5068 KB Output is correct
6 Correct 4 ms 5040 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 5324 KB Output is correct
10 Correct 4 ms 4968 KB Output is correct
11 Correct 6 ms 5068 KB Output is correct
12 Correct 13 ms 5580 KB Output is correct
13 Correct 10 ms 5736 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 5 ms 5068 KB Output is correct
16 Correct 1579 ms 68336 KB Output is correct
17 Correct 156 ms 28612 KB Output is correct
18 Correct 195 ms 28852 KB Output is correct
19 Correct 1926 ms 90264 KB Output is correct
20 Correct 774 ms 73624 KB Output is correct
21 Correct 72 ms 12808 KB Output is correct
22 Correct 658 ms 67948 KB Output is correct