oj.uz

Submission #37409

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122624 KB Output is correct
2 Correct 0 ms 122624 KB Output is correct
3 Correct 0 ms 122624 KB Output is correct
4 Correct 3 ms 122760 KB Output is correct
5 Correct 3 ms 122756 KB Output is correct
6 Correct 3 ms 122624 KB Output is correct
7 Correct 0 ms 122760 KB Output is correct
8 Correct 0 ms 122760 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 122756 KB Output is correct
2 Correct 0 ms 122624 KB Output is correct
3 Correct 0 ms 122756 KB Output is correct
4 Correct 6 ms 122888 KB Output is correct
5 Correct 3 ms 122888 KB Output is correct
6 Correct 0 ms 122624 KB Output is correct
7 Correct 3 ms 122756 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 149280 KB Output is correct
2 Correct 99 ms 127376 KB Output is correct
3 Correct 116 ms 128564 KB Output is correct
4 Correct 946 ms 153172 KB Output is correct
5 Correct 393 ms 145512 KB Output is correct
6 Correct 46 ms 125000 KB Output is correct
7 Correct 389 ms 140972 KB Output is correct