oj.uz

Submission #345727

# Submission time Handle Problem Language Result Execution time Memory
345727 2021-01-08T01:46:12 Z casperwang Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 691 ms 89364 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.clear();
  path.resize(N);
  dis.clear();
  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();
    if (d != dis[now].ss) continue;
    for (pii e : path[now]) {
      ll id = e.ff, c = e.ss;
      if (d + c <= dis[id].ff) {
        dis[id].ss = dis[id].ff;
        dis[id].ff = d + c;
        if (dis[id].ss != INF)
          nxt.push(pii(dis[id].ss, id));
      } else if (d + c < dis[id].ss) {
        dis[id].ss = d + c;
        nxt.push(pii(dis[id].ss, id));
      }
    }
  }
  return dis[0].ss;
}

Subtask #1
46.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 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct

Subtask #2
43.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 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 4 ms 1132 KB Output is correct
13 Correct 4 ms 1132 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct

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 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 4 ms 1132 KB Output is correct
13 Correct 4 ms 1132 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 562 ms 81696 KB Output is correct
17 Correct 78 ms 17644 KB Output is correct
18 Correct 108 ms 20076 KB Output is correct
19 Correct 691 ms 89364 KB Output is correct
20 Correct 321 ms 65920 KB Output is correct
21 Correct 38 ms 8172 KB Output is correct
22 Incorrect 326 ms 62572 KB Output isn't correct