oj.uz

Submission #345738

# Submission time Handle Problem Language Result Execution time Memory
345738 2021-01-08T01:57:54 Z casperwang Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 703 ms 73056 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;
vector <bool> vis;
priority_queue <pii, vector<pii>, greater<pii>> nxt;
 
void init(int N) {
  path.clear();
  path.resize(N);
  dis.clear();
  dis.resize(N);
  vis.clear();
  vis.resize(N);
  for (int i = 0; i < N; i++)
    dis[i].ff = dis[i].ss = INF;
  while (nxt.size()) nxt.pop();
}
 
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 (vis[now]) continue;
    vis[now] = 1;
    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 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 1004 KB Output is correct
13 Correct 3 ms 1004 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 524 KB Output is correct

Subtask #3
11.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 1004 KB Output is correct
13 Correct 3 ms 1004 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 524 KB Output is correct
16 Correct 566 ms 65636 KB Output is correct
17 Correct 80 ms 14444 KB Output is correct
18 Correct 108 ms 16748 KB Output is correct
19 Correct 703 ms 73056 KB Output is correct
20 Correct 328 ms 52844 KB Output is correct
21 Correct 40 ms 6764 KB Output is correct
22 Correct 336 ms 48364 KB Output is correct