Submission #64626

#	Time	Username	Problem	Language	Result	Execution time	Memory
64626		gnoor	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1484 ms	83944 KiB

crocodile

#include "crocodile.h"

#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

struct ei {
	int vec,wgt;
};

bool operator< (const ei &a, const ei &b) {
	return a.wgt>b.wgt;
}

int dis[100100];
int cnt[100100];
vector<ei> pth[100100];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	memset(dis,63,sizeof(dis));
	for (int i=0;i<M;i++) {
		pth[R[i][0]].push_back(ei{R[i][1],L[i]});
		pth[R[i][1]].push_back(ei{R[i][0],L[i]});
	}
	priority_queue<ei> q;
	for (int i=0;i<K;i++) {
		cnt[P[i]]=1;
		q.push(ei{P[i],0});	
	}
	int now,nowdis;
	while (!q.empty()) {
		now=q.top().vec;
		nowdis=q.top().wgt;
		q.pop();
		cnt[now]++;
		if (cnt[now]!=2) continue;
		dis[now]=nowdis;
		for (auto &i:pth[now]) {
			q.push(ei{i.vec,dis[now]+i.wgt});
		}
	}
	return dis[0];
}

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