Submission #261859

#	Time	Username	Problem	Language	Result	Execution time	Memory
261859		Sakamotoo	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	908 ms	74472 KiB

crocodile

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

#define mp make_pair
#define fi first
#define se second

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
	priority_queue<long long> jar[n+10];
	vector<pair<long long, long long> > adj[n+10];
	for(int i=0; i<m; i++){
		adj[r[i][0]].push_back(mp(r[i][1],l[i]));
		adj[r[i][1]].push_back(mp(r[i][0],l[i]));
	}
	
	priority_queue<pair<long long, long long> > pq;
	
	for(int i=0; i<k; i++){
		jar[p[i]].push(0);
		jar[p[i]].push(0);
		pq.push(mp(0,p[i]));
	}
	
	while(!pq.empty()){
		long long x=-pq.top().fi,y=pq.top().se;
		pq.pop();
		if(jar[y].top()<x) continue;
		if(x>1e9) continue;
		for(int i=0; i<adj[y].size(); i++){
			long long ind=adj[y][i].fi,cost=adj[y][i].se;
			
			if(jar[ind].size()<2){
				jar[ind].push(x+cost);
				if(jar[ind].size()==2){
					pq.push(mp(-jar[ind].top(),ind));
				}
			}else{
				if(jar[ind].top()>x+cost){
					jar[ind].pop();
					jar[ind].push(x+cost);
					pq.push(mp(-jar[ind].top(),ind));
				}
			}
		}
	}
	return jar[0].top();
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<adj[y].size(); i++){
                ~^~~~~~~~~~~~~~

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