Submission #633574

#	Time	Username	Problem	Language	Result	Execution time	Memory
633574		l_reho	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	1 ms	212 KiB

crocodile

#include "crocodile.h"


#include <bits/stdc++.h>
using namespace std;

vector<int> dp;
vector<vector<pair<int, int>>> graph;
vector<bool> visited;
int inf = 1e9+5;

struct info{
	int node;
	int start;
	int dist;
	
	bool operator< (const info& rhs) const {
        return dist > rhs.dist;
    }
	
};

void dijkstra(vector<int> ends){
	
	priority_queue<info> pq;
	
	
	for(int e : ends)
		pq.push({e, e, 0}), dp[e] = 0;
	
	while(!pq.empty()){
		
		info p = pq.top();
	
		pq.pop();
		
		vector<pair<int, int>> adj = graph[p.node];
		
		for(pair<int, int> a : adj){
			
			if(dp[p.node] + a.second < dp[a.first]){
				dp[a.first] = dp[p.node] + a.second;
				pq.push({a.first, p.start, dp[a.first]});
			} 
			
			
		}
	}

	
}

extern int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	dp.assign(N, inf);
	visited.assign(N, 0);
	
	graph.assign(N, vector<pair<int, int>>());
	
	for(int i = 0; i < M; i++){
		graph[R[i][0]].push_back({R[i][1], L[i]});
		graph[R[i][1]].push_back({R[i][0], L[i]});
		
	}
	vector<int> ends;
	unordered_map<int, bool> end;
	for(int i = 0; i < K; i++)
		ends.push_back(P[i]), end[P[i]] = true;
		
	dijkstra(ends);
	
	int curr = 0, ans = 0;
	
	while(!end[curr]){
		visited[curr] = 1;
		vector<pair<int, int>> adj = graph[curr];
		
		deque<pair<int, int>> dq;
		
		for(pair<int, int> a : adj){
			if(visited[a.first]) continue;
			if(dq.empty()){
				dq.push_back({dp[a.first] + a.second, a.first});
				continue;
			}
			
			if((int) dq.size() == 1){
				if(dp[a.first] + a.second < dq.back().first) dq.push_back({dp[a.first] + a.second, a.first});
				else dq.push_front({dp[a.first] + a.second, a.first});
				
				continue;
			}
			
			if(dp[a.first] + a.second < dq.back().first) dq.pop_front(), dq.push_back({dp[a.first] + a.second, a.first});
			else if(dp[a.first] + a.second < dq.front().first) dq.pop_front(), dq.push_front({dp[a.first] + a.second, a.first});
		}
		
		curr = dq.front().second;
		ans += dq.front().first - dp[dq.front().second];
		
	}
	
	return ans;
}

• Subtask 1: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11