Submission #786062

#	Time	Username	Problem	Language	Result	Execution time	Memory
786062		KN200711	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	413 ms	100968 KiB

crocodile

#include "crocodile.h"
# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;

bool vis[100001], ct[100001];
ll nw[100001];
vector<pair<int, ll> > edge[100001];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for(int i=0;i<N;i++) {
		vis[i] = 0;
		ct[i] = 0;
		edge[i].clear();
	}
	for(int i=0;i<M;i++) {
		edge[R[i][0]].push_back(make_pair(R[i][1], L[i]));
		edge[R[i][1]].push_back(make_pair(R[i][0], L[i]));
	}
	for(int i=0;i<K;i++) vis[P[i]] = 1;
	
	priority_queue< pair<ll, int> > PQ;
	for(int i=0;i<K;i++) {
		for(int c=0;c<edge[P[i]].size();c++) {
			PQ.push(make_pair(-edge[P[i]][c].se, edge[P[i]][c].fi));
		}
	}
	
	while(!PQ.empty()) {
		ll a = -PQ.top().fi;
		int b = PQ.top().se;
		PQ.pop();
		
		if(vis[0]) break;
		if(vis[b]) continue;
		if(ct[b]) {
			nw[b] = a;
			vis[b] = 1;
			for(int k=0;k<edge[b].size();k++) {
				if(!vis[edge[b][k].fi]) PQ.push(make_pair(-a-edge[b][k].se, edge[b][k].fi));
			}
		} else ct[b] = 1;
	}
	
	return nw[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int c=0;c<edge[P[i]].size();c++) {
      |               ~^~~~~~~~~~~~~~~~~~
crocodile.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |    for(int k=0;k<edge[b].size();k++) {
      |                ~^~~~~~~~~~~~~~~

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