oj.uz

Submission #410340

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

using namespace std;

typedef long long ll;

mt19937 rng((long long) (new char));

const int N = 100000 + 7;
const int INF = (int) 1e9 + 7;
int n, m, k, best[N];
bool inside[N];
vector<pair<int, int>> lol[N];
vector<pair<int, int>> g[N];
queue<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;
  if (!inside[i]) {
    inside[i] = 1;
    q.push(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 < n; i++) {
    shuffle(g[i].begin(), g[i].end(), rng);
  }
  shuffle(ch, ch + k, rng);
  for (int i = 0; i < k; i++) {
    push(ch[i], 0);
  }
  int cnt = 0;
  while (!q.empty()) {
    int a = q.front();
    inside[a] = 0;
    q.pop();
    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:73:7: warning: unused variable 'cnt' [-Wunused-variable]
   73 |   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 3 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 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 5 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 3 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 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 7 ms 5324 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 6 ms 5068 KB Output is correct
12 Correct 13 ms 5604 KB Output is correct
13 Correct 12 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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 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 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 7 ms 5324 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 6 ms 5068 KB Output is correct
12 Correct 13 ms 5604 KB Output is correct
13 Correct 12 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 1792 ms 67184 KB Output is correct
17 Correct 186 ms 26584 KB Output is correct
18 Correct 1184 ms 26908 KB Output is correct
19 Execution timed out 2084 ms 73880 KB Time limit exceeded
20 Halted 0 ms 0 KB -