oj.uz

Submission #345733

# Submission time Handle Problem Language Result Execution time Memory
345733 2021-01-08T01:52:00 Z casperwang Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 685 ms 73076 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 = 1e17;
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 (int)dis[0].ss;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 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 0 ms 364 KB Output is correct
2 Correct 1 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 1004 KB Output is correct
13 Correct 4 ms 1004 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 0 ms 364 KB Output is correct
2 Correct 1 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 1004 KB Output is correct
13 Correct 4 ms 1004 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 570 ms 65588 KB Output is correct
17 Correct 79 ms 14444 KB Output is correct
18 Correct 106 ms 16748 KB Output is correct
19 Correct 685 ms 73076 KB Output is correct
20 Correct 328 ms 52844 KB Output is correct
21 Correct 39 ms 6764 KB Output is correct
22 Incorrect 336 ms 48364 KB Output isn't correct