Submission #335760

#	Time	Username	Problem	Language	Result	Execution time	Memory
335760		tevdore	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1159 ms	60080 KiB

crocodile

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

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	priority_queue < pair < int, int > > pq;
	vector < pair < int, int > > v[N + 1];
	long long d[N + 1], f[N + 1];
	memset(d, 0, sizeof d);
	memset(f, 0, sizeof f);
	for(int i = 0; i < M; i++) {
		v[R[i][0]].push_back({R[i][1], L[i]});
		v[R[i][1]].push_back({R[i][0], L[i]});
	}
	for(int i = 0; i < K; i++) pq.push({0, P[i]}), f[P[i]] = 1; 
	while(pq.size()) {
		pair < int, int > p = pq.top();
		pq.pop();
		int dist = p.first;
		int u = p.second;
		if(!f[u]) {
			f[u] = 1;
			continue;
		}
		if(f[u] == 2) continue;
		if(f[u] == 1) f[u] = 2;
		d[u] = -dist;
		for(auto x : v[u]) pq.push({dist - x.second, x.first});
	}
    return d[0];
}

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