oj.uz

Submission #499593

# Submission time Handle Problem Language Result Execution time Memory
499593 2021-12-28T22:19:17 Z aryan12 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 545 ms 93440 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

const long long MAXN = 1e5 + 5;
set<long long> exits;
vector<pair<long long, long long> > g[MAXN];
long long values[MAXN][2];
bool vis[MAXN];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  for(long long i = 0; i < MAXN; i++) {
    values[i][0] = 1e15;
    values[i][1] = 1e15;
  }
  for(long long i = 0; i < K; i++) {
    exits.insert(P[i]);
  }
  for(long long 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]});
  }
  for(long long i = 0; i < N; i++) {
    if(exits.count(i)) {
      for(long long j = 0; j < g[i].size(); j++) {
        int hi = g[i][j].first;
        if(!exits.count(hi)) {
          if(values[hi][1] < g[i][j].second) {
            continue;
          }
          else if(values[hi][0] < g[i][j].second) {
            values[hi][1] = g[i][j].second;
          }
          else {
            values[hi][1] = values[hi][0];
            values[hi][0] = g[i][j].second;
          }
        }
      }
    }
  }
  priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > > pq;
  for(long long i = 0; i < N; i++) {
    if(values[i][1] != 1e15) {
      pq.push({values[i][1], i});
    }
  }
  while(!pq.empty()) {
    pair<long long, long long> cur = pq.top();
    pq.pop();
    long long cur_dist = cur.first, node = cur.second;
    if(vis[node]) {
      continue;
    }
    if(node == 0) {
      break;
    }
    vis[node] = true;
    for(long long i = 0; i < g[node].size(); i++) {
      if(exits.count(g[node][i].first) || vis[g[node][i].first]) {
        continue;
      }
      long long new_dist = g[node][i].second + cur_dist;
      long long next = g[node][i].first;
      //cout << "node = " << node << ", next = " << next << ", cur_dist = " << cur_dist << ", new_dist = " << new_dist << endl;
      if(values[next][1] < new_dist) {
        continue;
      }
      else if(values[next][0] < new_dist) {
        //assert(!vis[g[node][i].first]);
        values[next][1] = new_dist;
        pq.push({values[next][1], next});
      }
      else {
        //assert(!vis[g[node][i].first]);
        values[next][1] = values[next][0];
        values[next][0] = new_dist;
        pq.push({values[next][1], next});
      }
    }
  }
  while(!pq.empty()) {
    pq.pop();
  }
  /*for(int i = 0; i < N; i++) {
    cout << values[i][0] << " " << values[i][1] << endl;
  }*/
  assert(values[0][1] != 1e15);
  return values[0][1];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:25:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |       for(long long j = 0; j < g[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~
crocodile.cpp:59:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(long long i = 0; i < g[node].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 2 ms 4172 KB Output is correct
4 Correct 4 ms 4320 KB Output is correct
5 Correct 3 ms 4332 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 3 ms 4300 KB Output is correct
8 Correct 3 ms 4328 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 2 ms 4172 KB Output is correct
4 Correct 4 ms 4320 KB Output is correct
5 Correct 3 ms 4332 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 3 ms 4300 KB Output is correct
8 Correct 3 ms 4328 KB Output is correct
9 Correct 4 ms 4584 KB Output is correct
10 Correct 3 ms 4192 KB Output is correct
11 Correct 4 ms 4360 KB Output is correct
12 Correct 5 ms 4972 KB Output is correct
13 Correct 5 ms 4960 KB Output is correct
14 Correct 2 ms 4172 KB Output is correct
15 Correct 3 ms 4300 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 2 ms 4172 KB Output is correct
4 Correct 4 ms 4320 KB Output is correct
5 Correct 3 ms 4332 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 3 ms 4300 KB Output is correct
8 Correct 3 ms 4328 KB Output is correct
9 Correct 4 ms 4584 KB Output is correct
10 Correct 3 ms 4192 KB Output is correct
11 Correct 4 ms 4360 KB Output is correct
12 Correct 5 ms 4972 KB Output is correct
13 Correct 5 ms 4960 KB Output is correct
14 Correct 2 ms 4172 KB Output is correct
15 Correct 3 ms 4300 KB Output is correct
16 Correct 542 ms 85876 KB Output is correct
17 Correct 97 ms 19816 KB Output is correct
18 Correct 112 ms 21304 KB Output is correct
19 Correct 545 ms 93440 KB Output is correct
20 Correct 276 ms 69616 KB Output is correct
21 Correct 43 ms 11476 KB Output is correct
22 Correct 305 ms 65672 KB Output is correct