Submission #301369

#	Time	Username	Problem	Language	Result	Execution time	Memory
301369		errorgorn	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	746 ms	93340 KiB

crocodile

#include "crocodile.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int n,m,k;
vector<ii> al[100005];
ii w[100005];
bool vis[100005];
priority_queue<ii,vector<ii>,greater<ii> > pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n=N,m=M,k=K;
	
	memset(w,63,sizeof(w));
	
	rep(x,0,m){
		al[R[x][0]].push_back(ii(R[x][1],L[x]));
		al[R[x][1]].push_back(ii(R[x][0],L[x]));
	}
	
	rep(x,0,k){
		w[P[x]]=ii(0,0);
		pq.push(ii(0,P[x]));
	}
	
	int weight,node;
	while (!pq.empty()){
		tie(weight,node)=pq.top(),pq.pop();
		
		if (weight!=w[node].se || vis[node]) continue;
		vis[node]=true;
		
		if (node==0) return weight;
		
		for (auto &it:al[node]) if (!vis[it.fi]){
			if (w[it.fi].se>weight+it.se){
				w[it.fi].se=weight+it.se;
				if (w[it.fi].fi>w[it.fi].se) swap(w[it.fi].fi,w[it.fi].se);
				
				pq.push(ii(w[it.fi].se,it.fi));
			}
		}
	}
	
	return -1;
}

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