Submission #499593

#	Time	Username	Problem	Language	Result	Execution time	Memory
499593		aryan12	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	545 ms	93440 KiB

crocodile

#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 (stderr)

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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11