Submission #121104

#	Time	Username	Problem	Language	Result	Execution time	Memory
121104		turbat	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	810 ms	57460 KiB

crocodile

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

vector <pair <int , int> > edg[100005];
 
bool vis[100005][2];
long long dist[100005][2];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	for (int i = 0;i < N;i++) 
		dist[i][0] = dist[i][1] = 2e9;
	for (int i = 0;i < M;i++) {
		edg[R[i][0]].push_back(make_pair(R[i][1], L[i]));
		edg[R[i][1]].push_back(make_pair(R[i][0], L[i]));
	}
	priority_queue <pair <long long, int> > que;
	for (int i = 0;i < K;i++){
		que.push(make_pair(0, P[i]));
		vis[P[i]][0] = 1;
		dist[P[i]][0] = dist[P[i]][1] = 0;
	}
	while (!que.empty()){		
		int u = que.top().second;
		long long cost = -que.top().first;
		if (dist[u][1] > cost) dist[u][1] = cost;
		if (dist[u][0] > dist[u][1]) swap(dist[u][0], dist[u][1]);
		cost = dist[u][1];
		// if (vis[u][0]) cout << u<< ' '<< cost << endl;
		if (vis[u][0]){
			vis[u][1] = 1;
			for (auto v : edg[u])
				if (!vis[v.first][1] && dist[v.first][1] > cost + v.second){
					dist[v.first][1] = cost + v.second;
					if (dist[v.first][0] > dist[v.first][1]) swap(dist[v.first][0], dist[v.first][1]);
					que.push(make_pair(-dist[v.first][1], v.first));
				}
		}
		else vis[u][0] = 1;
		while (!que.empty() && vis[que.top().second][1])
			que.pop();
	}
	return dist[0][1];
}

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