Submission #37409

#	Time	Username	Problem	Language	Result	Execution time	Memory
37409		szawinis	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	946 ms	153172 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1e5+1, INF = 1e9+1;

int n, m, d[N][2];
vector<int> e;
vector<pii> g[N];
priority_queue<pii, vector<pii>, greater<pii> > pq;
bool mark[N];

int travel_plan(int _n, int _m, int _edges[][2], int _w[], int _k, int _p[]) {
  n = _n, m = _m;
  for(int i = 0; i < m; i++) {
    g[_edges[i][0]].emplace_back(_edges[i][1], _w[i]);
    g[_edges[i][1]].emplace_back(_edges[i][0], _w[i]);
  }
  for(int i = 0; i < n; i++) d[i][0] = d[i][1] = INF;
  for(int i = 0; i < _k; i++) {
    e.push_back(_p[i]);
    d[e[i]][0] = d[e[i]][1] = 0;
    pq.emplace(0, e[i]);
  }
  while(!pq.empty()) {
    int u, curr_dist; tie(curr_dist, u) = pq.top();
    pq.pop();
    if(mark[u]) continue;
    mark[u] = true;
    for(auto p: g[u]) {
      int v, w; tie(v, w) = p;
      if(d[u][1] + w < d[v][0]) {
        d[v][1] = d[v][0];
        d[v][0] = d[u][1] + w;
        if(d[v][1] != INF) pq.emplace(d[v][1], v);
      } else if(d[u][1] + w < d[v][1]) {
        d[v][1] = d[u][1] + w;
        pq.emplace(d[v][1], v);
      }
    }
  }
  return d[0][1];
}

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