Submission #946579

#	Time	Username	Problem	Language	Result	Execution time	Memory
946579		StefanSebez	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	2 ms	6492 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
const int N=1e5+50,inf=1e9;
vector<pair<int,int> >E[N];
map<pair<int,int>,bool>mapa;
map<pair<int,int>,int>grana;
bool nesto[N];
int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
	for(int i=0;i<m;i++){
		E[R[i][0]].pb({R[i][1],L[i]}),E[R[i][1]].pb({R[i][0],L[i]});
		grana[{R[i][0],R[i][1]}]=grana[{R[i][1],R[i][0]}]=L[i];
	}
	for(int i=0;i<K;i++) nesto[P[i]]=true;
	int U=0,res=0;
	while(!nesto[U]){
		//printf("%i\n",U);
		int dist[n+10],parent[n+10];
		memset(parent,-1,sizeof(parent));
		for(int i=0;i<n;i++) dist[i]=inf;
		dist[U]=0;
		priority_queue<pair<int,int> >pq;
		pq.push({0,U});
		while(!pq.empty()){
			int u=pq.top().se,w=-pq.top().fi;
			pq.pop();
			if(w>dist[u]) continue;
			for(auto i:E[u]){
				if(mapa[{i.fi,u}]) continue;
				if(dist[i.fi]>dist[u]+i.se){
					dist[i.fi]=dist[u]+i.se;
					parent[i.fi]=u;
					pq.push({-dist[i.fi],i.fi});
				}
			}
		}
		/*for(int i=0;i<n;i++) printf("%i: %i %i\n",i,dist[i],parent[i]);
		printf("\n");*/
		int mn=0;
		for(int i=0;i<K;i++) if(dist[P[i]]<dist[P[mn]]) mn=i;
		int tmp=mn;mn=P[mn];
		//printf("%i %i\n",tmp,mn);
		while(parent[mn]!=U) mn=parent[mn];
		mapa[{U,mn}]=mapa[{mn,U}]=true;
		mn=0;if(tmp==0) mn=K-1;
		for(int i=0;i<K;i++) if(dist[P[i]]<dist[P[mn]] && i!=tmp) mn=i;
		mn=P[mn];
		while(parent[mn]!=U) mn=parent[mn];
		mapa[{U,mn}]=mapa[{mn,U}]=true;
		res+=grana[{U,mn}];
		U=mn;
		//printf("%i\n",mn);
	}
	return res;
}

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