Submission #527543

#	Time	Username	Problem	Language	Result	Execution time	Memory
527543		Cantfindme	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	490 ms	73996 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
 
const ll maxn = 100010;
 
ll vis[maxn];
ll dist1[maxn], dist2[maxn];
vector <pi> adjlist[maxn];
ll n, e;
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N; e = M;
	
	for (ll i =0;i<e;i++) {
		ll a = R[i][0], b = R[i][1], c = L[i];
		adjlist[a].push_back(pi(b,c));
		adjlist[b].push_back(pi(a,c));
	}
	
	priority_queue <pi, vector<pi>, greater<pi>> pq;
	memset(dist1,-1,sizeof dist1);
	memset(dist2,-1,sizeof dist2);
	
	for (ll i =0;i<K;i++) {
		pq.push(pi(0, P[i]));
		dist1[P[i]] = dist2[P[i]] = 0;
	}
	
	while (!pq.empty()) {
		auto [d, x] = pq.top(); pq.pop();
		if (vis[x]) continue;
		vis[x] = 1;
		
		for (auto [i, c]: adjlist[x]) {
			if (dist1[i] == -1) {
				dist1[i] = d + c;
			} else if (dist2[i] == -1) {
				dist2[i] = d + c;
				if (dist2[i] < dist1[i]) swap(dist1[i], dist2[i]);
				pq.push(pi(dist2[i], i));
			} else if (d + c < dist2[i]) {
				dist2[i] = d + c;
				if (dist2[i] < dist1[i]) swap(dist1[i], dist2[i]);
				pq.push(pi(dist2[i], i));
			}
		}
	}
	
	//for (int i =0;i<n;i++) {
		//cout << i << " " << dist1[i] << " " << dist2[i] << "\n";
	//}
	
	return dist2[0];
}
 

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