oj.uz

Submission #228379

# Submission time Handle Problem Language Result Execution time Memory
228379 2020-04-30T20:31:30 Z tushar_2658 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 720 ms 93412 KB 
#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std;

const int maxn = 100005;
using ll = long long;

vector<pair<int, ll>> edges[maxn];
ll dis[maxn][2];
bool vis[maxn];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{	
  for(int i = 0; i < M; ++i){
  	edges[R[i][0]].push_back(make_pair(R[i][1], L[i]));
  	edges[R[i][1]].push_back(make_pair(R[i][0], L[i]));
  }
  using pii = pair<ll, int>;
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  memset(dis, 63, sizeof dis);
  for(int i = 0; i < K; ++i){
  	pq.push(make_pair(0, P[i]));
  	dis[P[i]][0] = dis[P[i]][1] = 0;
  }
  while(!pq.empty()){
  	pii s = pq.top();
  	pq.pop();
  	if(vis[s.second])continue;
  	vis[s.second] = 1;
  	for(auto i : edges[s.second]){
  		ll cost = dis[s.second][1] + i.second;
  		if(dis[i.first][0] >= cost){
  			dis[i.first][1] = dis[i.first][0];
  			dis[i.first][0] = cost;
  			pq.push(make_pair(dis[i.first][1], i.first));
  		}else if(dis[i.first][1] > cost){
  			dis[i.first][1] = cost;
  			pq.push(make_pair(dis[i.first][1], i.first));
  		}
  	}
  }
  return dis[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 6 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 7 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 6 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 7 ms 4352 KB Output is correct
9 Correct 11 ms 4608 KB Output is correct
10 Correct 7 ms 4352 KB Output is correct
11 Correct 8 ms 4528 KB Output is correct
12 Correct 10 ms 4992 KB Output is correct
13 Correct 10 ms 5120 KB Output is correct
14 Correct 7 ms 4352 KB Output is correct
15 Correct 8 ms 4352 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 6 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 7 ms 4352 KB Output is correct
9 Correct 11 ms 4608 KB Output is correct
10 Correct 7 ms 4352 KB Output is correct
11 Correct 8 ms 4528 KB Output is correct
12 Correct 10 ms 4992 KB Output is correct
13 Correct 10 ms 5120 KB Output is correct
14 Correct 7 ms 4352 KB Output is correct
15 Correct 8 ms 4352 KB Output is correct
16 Correct 570 ms 85608 KB Output is correct
17 Correct 114 ms 19948 KB Output is correct
18 Correct 149 ms 22384 KB Output is correct
19 Correct 720 ms 93412 KB Output is correct
20 Correct 349 ms 69244 KB Output is correct
21 Correct 55 ms 11640 KB Output is correct
22 Correct 387 ms 65784 KB Output is correct