oj.uz

Submission #345722

# Submission time Handle Problem Language Result Execution time Memory
345722 2021-01-08T01:33:34 Z casperwang Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 1 ms 364 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define pii pair<ll,ll>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 100000;
const ll INF = 1e18;
vector <vector<pii>> path;
vector <pii> dis;
priority_queue <pii, vector<pii>, greater<pii>> nxt;

void init(int N) {
  path.resize(N);
  dis.resize(N);
  for (int i = 0; i < N; i++)
    dis[i].ff = dis[i].ss = INF;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  init(N);
  for (int i = 0; i < M; i++) {
    path[R[i][0]].pb(R[i][1], L[i]);
    path[R[i][1]].pb(R[i][0], L[i]);
  }
  for (int i = 0; i < K; i++) {
    dis[P[i]].ff = dis[P[i]].ss = 0;
    nxt.push(pii(0, P[i]));
  }
  while (nxt.size()) {
    ll now = nxt.top().ss, d = nxt.top().ff;
    nxt.pop();
    for (pii e : path[now]) {
      int id = e.ff, c = e.ss;
      if (d + c < dis[id].ff) {
        dis[id].ss = dis[id].ff;
        dis[id].ff = d + c;
      } else if (d + c < dis[id].ss) {
        dis[id].ss = d + c;
      } else {
        continue;
      }
      if (dis[id].ss != INF)
        nxt.push(pii(dis[id].ss, id));
    }
  }
  return dis[0].ss;
}

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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