Submission #402726

#	Time	Username	Problem	Language	Result	Execution time	Memory
402726		Cantfindme	Crocodile's Underground City (IOI11_crocodile)	C++17	89 / 100	599 ms	73808 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 int maxn = 100010;

ll state[maxn];
ll dist[maxn], distreal[maxn];
vector <pi> adjlist[maxn];
int n, e;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N; e = M;
	
	for (int i =0;i<e;i++) {
		int 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(dist,-1,sizeof dist);
	memset(distreal,-1,sizeof distreal);
	
	for (int i =0;i<K;i++) {
		pq.push(pi(0, P[i]));
		distreal[P[i]] = 0;
		state[P[i]] = 2;
	}
	
	while (!pq.empty()) {
		auto [d,x] = pq.top(); pq.pop();
		if (d != distreal[x]) continue;
		
		
		for (auto [i,c] : adjlist[x]) {
			
			if (state[i] == 0) {
				state[i] = 1;
				dist[i] = c + d;
			} else if (state[i] == 1) {
				if (distreal[i] == -1 or distreal[i] > c + d) {
					distreal[i] = c + d;
					if (distreal[i] < dist[i]) swap(dist[i],distreal[i]);
										
					pq.push(pi(distreal[i],i));
				}
			}
		}
	}
	
	return distreal[0];
}

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