Submission #235993

#	Time	Username	Problem	Language	Result	Execution time	Memory
235993		cfalas	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	695 ms	113084 KiB

crocodile

#include<bits/stdc++.h>
using namespace std;
#include "crocodile.h"
#define F first
#define S second
typedef pair<int, int> ii;
typedef vector<ii> vii;

vector<vii> adj;
#define INF 1500000000
map<int, bool> child[1000000];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	adj.assign(n+1, vii());
	for(int i=0;i<m;i++){
		adj[r[i][0]].push_back(ii(r[i][1],l[i]));
		adj[r[i][1]].push_back(ii(r[i][0],l[i]));
	}
	priority_queue<ii> q;
	for(int i=0;i<k;i++){
		q.push(ii(0, p[i]));
		q.push(ii(0, p[i]));
	}
	int cnt[n+1] = {};
	int ans=0;
	while(!q.empty()){
		ii t = q.top();
		q.pop();
		cnt[t.S]++;
		if(cnt[t.S]!=2) continue;
		if(t.S==0){ans=-t.F;break;}
		for(auto x : adj[t.S]){
			q.push(ii(-x.S+t.F, x.F));
		}
	}
	return ans;
}

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