oj.uz

Submission #37408

# Submission time Handle Problem Language Result Execution time Memory
37408 2017-12-25T08:01:49 Z szawinis Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 946 ms 150720 KB 
#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;
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();
    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
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122528 KB Output is correct
2 Correct 0 ms 122528 KB Output is correct
3 Incorrect 0 ms 122528 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 122660 KB Output is correct
2 Correct 0 ms 122528 KB Output is correct
3 Incorrect 3 ms 122660 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 946 ms 150720 KB Output isn't correct
2 Halted 0 ms 0 KB -