oj.uz

Submission #588558

# Submission time Handle Problem Language Result Execution time Memory
588558 2022-07-03T14:03:54 Z M_W Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 515 ms 91644 KB 
#include <bits/stdc++.h>
#define ii pair<long long, long long>
using namespace std;
vector<ii> adj2[100001], adj[100001];
long long dist[100001][2];
int cnt[100001];
bitset<100001> mark;

void dfs(int a, int p){
	printf("!>> %d %d\n", a, p);
	mark[a] = 1;
	if(a != 0 && adj2[a].size() <= 2) return;
	for(auto [x, w] : adj2[a]){
		if(x == p) continue;
		adj[a].push_back({x, w});
		adj[x].push_back({a, w});
		if(!mark[x]) dfs(x, a);
	} 
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for(int i = 0; i < M; i++){
		adj[R[i][0]].push_back({R[i][1], L[i]});
		adj[R[i][1]].push_back({R[i][0], L[i]});
	}
	// dfs(0, 0);

	priority_queue<ii, vector<ii>, greater<ii>> pq;
	for(int i = 0; i < N; i++) dist[i][0] = dist[i][1] = LLONG_MAX;
	for(int i = 0; i < K; i++){
		if(1 | mark[P[i]]){
			pq.push({0, P[i]});
			dist[P[i]][0] = dist[P[i]][1] = 0;
		}
	}
	while(!pq.empty()){
		auto [d, n] = pq.top();
		pq.pop();
		
		// printf(">> %d : %lld %lld\n", n, dist[n][0], dist[n][1]);
		
		if(dist[n][1] != d) continue;
		
		for(auto [x, w] : adj[n]){
			if(dist[x][0] > dist[n][1] + w){
				if(dist[x][1] > dist[x][0]){
					dist[x][1] = dist[x][0];
					pq.push({dist[x][1], x});
				}
				dist[x][0] = dist[n][1] + w;
			}
			else if(dist[x][1] > dist[n][1] + w){
				dist[x][1] = dist[n][1] + w;
				pq.push({dist[x][1], x});
			}
		}
	}
	return dist[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 3 ms 5016 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 4 ms 5064 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 3 ms 5016 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 4 ms 5064 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 3 ms 5020 KB Output is correct
11 Correct 5 ms 5156 KB Output is correct
12 Correct 7 ms 5768 KB Output is correct
13 Correct 5 ms 5792 KB Output is correct
14 Correct 3 ms 5024 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4960 KB Output is correct
3 Correct 3 ms 5016 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 4 ms 5064 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 3 ms 5020 KB Output is correct
11 Correct 5 ms 5156 KB Output is correct
12 Correct 7 ms 5768 KB Output is correct
13 Correct 5 ms 5792 KB Output is correct
14 Correct 3 ms 5024 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 424 ms 85256 KB Output is correct
17 Correct 70 ms 20044 KB Output is correct
18 Correct 100 ms 22568 KB Output is correct
19 Correct 515 ms 91644 KB Output is correct
20 Correct 262 ms 70392 KB Output is correct
21 Correct 37 ms 12024 KB Output is correct
22 Correct 302 ms 66396 KB Output is correct