Submission #197835

#	Time	Username	Problem	Language	Result	Execution time	Memory
197835		Sakamotoo	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	781 ms	64488 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[]){
	vector<pair<int,int> > adj[n];
	long long a[n],b[n];
	for(int i=0; i<n; i++){
		a[i]=1e18;
		b[i]=1e18;
	}
	int s[n];
	memset(s,0,sizeof s);
	for(int i=0; i<k; i++){
		s[p[i]]=1;
	}
	for(int i=0; i<m; i++){
		int x=r[i][0],y=r[i][1];
		if(s[y]==1) swap(x,y);
		long long sim=l[i];
		if(s[x]==1){
			if(a[y]>sim){
				swap(a[y],sim);
			}
			if(b[y]>sim){
				swap(b[y],sim);
			}
		}else {
			adj[x].push_back(mp(y,sim));
			adj[y].push_back(mp(x,sim));
		}
	}
	priority_queue<pair<long long, long long> > pq;
	for(int i=0; i<n; i++){
		if(b[i]<1e18&&s[i]==0){
			pq.push(mp(-b[i],i));
		}
	}
	while(!pq.empty()){
		long long x=-pq.top().fi,y=pq.top().se;
		pq.pop();
		if(x>b[y]) continue;
		for(int i=0; i<adj[y].size(); i++){
			long long z=adj[y][i].fi;
			long long c=adj[y][i].se+x;
			bool ada=0;
			if(c<a[z]){
				swap(c,a[z]);
			}
			if(c<b[z]){
				ada=1;
				swap(c,b[z]);
			}
			if(ada)pq.push(mp(-b[z],z));
		}
	}
	return b[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:47: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: 11 / 11