oj.uz

Submission #229795

# Submission time Handle Problem Language Result Execution time Memory
229795 2020-05-06T14:17:18 Z quocnguyen1012 Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 668 ms 47852 KB 
#ifndef LOCAL
#include "crocodile.h"
#endif // LOCAL

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;
const ll inf = 1e17;

int N, M, K;
ll dist[maxn][2];
vector<ii> adj[maxn];

int travel_plan(int _N, int _M, int R[][2], int L[], int _K, int P[])
{
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  N = _N, M = _M, K = _K;
  for(int i = 0; i < M; ++i){
    adj[R[i][0]].eb(R[i][1], L[i]);
    adj[R[i][1]].eb(R[i][0], L[i]);
    ///cerr << R[i][0] << ' ' << R[i][1] << ' ' << L[i] << '\n';
  }
  fill_n(&dist[0][0], maxn * 2, inf);
  for(int i = 0; i < K; ++i){
    pq.push(mp(0, P[i]));
    dist[P[i]][0] = dist[P[i]][1] = 0;
  }
  while(pq.size()){
    ll now; int u;
    tie(now, u) = pq.top(); pq.pop();
    if(now > dist[u][1]) continue;
    for(auto v : adj[u]){
      ll d = dist[u][1] + v.se;
      if(dist[v.fi][0] > d){
        swap(dist[v.fi][0], dist[v.fi][1]);
        dist[v.fi][0] = d;
        if(dist[v.fi][1] != inf)
          pq.push(mp(dist[v.fi][1], v.fi));
      }
      else if(dist[v.fi][1] > d){
        dist[v.fi][1] = d;
        pq.push(mp(d, v.fi));
      }
    }
    ///cerr << '\n';
  }
  return dist[0][1];
}

#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int _N, _M, _K;
  cin >> _N >> _M >> _K;
  int L[_M], R[_M][2], P[_K];
  for(int i = 0; i < _M; ++i){
    cin >> R[i][0] >> R[i][1];
  }
  for(int i = 0; i < _M; ++i)
    cin >> L[i];
  for(int i = 0; i < _K; ++i)
  cin >> P[i];
  cout << travel_plan(_N, _M, R, L, _K, P);
}
#endif // LOCAL

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4224 KB Output is correct
3 Correct 7 ms 4224 KB Output is correct
4 Correct 7 ms 4352 KB Output is correct
5 Correct 7 ms 4352 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 7 ms 4352 KB Output is correct
8 Correct 8 ms 4352 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4224 KB Output is correct
3 Correct 7 ms 4224 KB Output is correct
4 Correct 7 ms 4352 KB Output is correct
5 Correct 7 ms 4352 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 7 ms 4352 KB Output is correct
8 Correct 8 ms 4352 KB Output is correct
9 Correct 8 ms 4480 KB Output is correct
10 Correct 7 ms 4224 KB Output is correct
11 Correct 7 ms 4352 KB Output is correct
12 Correct 10 ms 4608 KB Output is correct
13 Correct 9 ms 4736 KB Output is correct
14 Correct 8 ms 4352 KB Output is correct
15 Correct 7 ms 4352 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4224 KB Output is correct
3 Correct 7 ms 4224 KB Output is correct
4 Correct 7 ms 4352 KB Output is correct
5 Correct 7 ms 4352 KB Output is correct
6 Correct 7 ms 4352 KB Output is correct
7 Correct 7 ms 4352 KB Output is correct
8 Correct 8 ms 4352 KB Output is correct
9 Correct 8 ms 4480 KB Output is correct
10 Correct 7 ms 4224 KB Output is correct
11 Correct 7 ms 4352 KB Output is correct
12 Correct 10 ms 4608 KB Output is correct
13 Correct 9 ms 4736 KB Output is correct
14 Correct 8 ms 4352 KB Output is correct
15 Correct 7 ms 4352 KB Output is correct
16 Correct 517 ms 43376 KB Output is correct
17 Correct 100 ms 11256 KB Output is correct
18 Correct 116 ms 12664 KB Output is correct
19 Correct 668 ms 47852 KB Output is correct
20 Correct 331 ms 38136 KB Output is correct
21 Correct 51 ms 7544 KB Output is correct
22 Incorrect 367 ms 33144 KB Output isn't correct