Submission #467056

#	Time	Username	Problem	Language	Result	Execution time	Memory
467056		Autron	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	643 ms	63288 KiB

crocodile

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

struct elem{
	int x;
	int dist1, dist2;
	bool operator<(const elem &ot) const{
		if(dist2!=ot.dist2) return dist2>ot.dist2;
		return dist1>ot.dist1;
	}
};

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
	vector<vector<pair<int, int>>> g(n+1);
	vector<bool> used(n+1, 0);
	vector<int> dist1(n+1, 1e9), dist2(n+1, 1e9);
	priority_queue<elem> pq;
	for(int i=0;i<m;++i){
		g[r[i][0]+1].push_back({r[i][1]+1, l[i]});
		g[r[i][1]+1].push_back({r[i][0]+1, l[i]});
	}
	for(int i=0;i<k;++i){
		dist1[p[i]+1]=dist2[p[i]+1]=0;
		pq.push({p[i]+1, dist1[p[i]+1], dist2[p[i]+1]});
	}
	while(!pq.empty()){
		elem x=pq.top();
		pq.pop();
		if(used[x.x]) continue;
		used[x.x]=1;
		for(auto it:g[x.x]){
			elem nx;
			nx.x=it.first;
			nx.dist1=dist1[it.first];
			nx.dist2=dist2[it.first];
			int ndist=x.dist2+it.second;
			if(ndist<=nx.dist1){
				nx.dist2=nx.dist1;
				nx.dist1=ndist;
				pq.push(nx);
			}
			else if(ndist<nx.dist2){
				nx.dist2=ndist;
				pq.push(nx);
			}
			dist1[nx.x]=nx.dist1;
			dist2[nx.x]=nx.dist2;
		}
	}
  return dist2[1];
}

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