Submission #169023

#	Time	Username	Problem	Language	Result	Execution time	Memory
169023		AlexLuchianov	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	680 ms	67304 KiB

crocodile

#include "crocodile.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;

struct Edge{
  int to;
  int cost;
  bool operator < (Edge const &a) const{
    return cost > a.cost;
  }
};
std::vector<Edge> g[1 + nmax];

int dpcount[1 + nmax], dp[1 + nmax];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  for(int 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]});
  }
  std::priority_queue<Edge> pq;
  for(int i = 0; i < K; i++) {
    dpcount[P[i]] = 1;
    pq.push({P[i], 0 });
  }

  while(0 < pq.size()){
    int node = pq.top().to;
    int cost = pq.top().cost;
    pq.pop();
    dpcount[node]++;
    if(dpcount[node] == 2){
      dp[node] = cost;
      if(node == 0)
        break;
      for(int h = 0; h < g[node].size(); h++){
        Edge e = g[node][h];
        if(dpcount[e.to] < 2)
          pq.push({e.to, dp[node] + e.cost});
      }
    }
  }

  if(dpcount[0] < 2)
    return -1;
  else
    return dp[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:45:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[node].size(); h++){
                      ~~^~~~~~~~~~~~~~~~

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11