oj.uz

Submission #381656

# Submission time Handle Problem Language Result Execution time Memory
381656 2021-03-25T13:04:49 Z BlancaHM Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 7 ms 492 KB 
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <unordered_set>
#include "crocodile.h"
using namespace std;

vector<vector<pair<int, int>>> adj;
//vector<int> dist;
unordered_set<int> dest;
vector<int> DP;

int dfs(int u, int par) {
	if (DP[u] != -1)
		return DP[u];
	if (dest.find(u) != dest.end())
		return DP[u] = 0;
	int shortest_child = INT_MAX, second_shortest = INT_MAX;
	for (auto curP: adj[u]) {
		if (curP.first == par)
			continue;
		int ans = dfs(curP.first, u) + curP.second;
		if (ans < shortest_child)
			shortest_child = ans;
		else if (ans < second_shortest)
			second_shortest = ans;
	}
	return DP[u] = second_shortest;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	// run Dijkstra with end vertices as sources

	adj.assign(N, vector<pair<int, int>>());
	for (int i = 0; i < M; i++) {
		adj[R[i][0]].push_back(make_pair(R[i][1], L[i]));
		adj[R[i][1]].push_back(make_pair(R[i][0], L[i]));
	}

	dest = unordered_set<int>();
	for (int i = 0; i < K; i++) {
		dest.insert(P[i]);
	}

	/*
	dist.assign(N, INT_MAX);
	priority_queue<pair<int, int>> pq; // {dist, node}
	for (int i = 0; i < K; i++) {
		pq.push(make_pair(0, P[i]));
		dist[P[i]] = 0;
	}

	while(!pq.empty()) {
		int node = pq.top().second();
		int cost = -pq.top().first();
		pq.pop();
		if (dist[node] < cost)
			continue;
		for (auto curP: adj[node]) {
			if (dist[node] + curP.second < dist[curP.first]) {
				dist[curP.first] = dist[node] + curP.second;
				pq.push(make_pair(-dist[curP.first], curP.first));
			}
		}
	}*/

	// find the answer recursively
	return dfs(0, -1);
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -