Submission #211399

#	Time	Username	Problem	Language	Result	Execution time	Memory
211399		socho	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	589 ms	50656 KiB

crocodile

#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define int long long

int n, m;
const int MXN = 100005;
vector<pair<int, int> > adj[MXN];
int vis[MXN];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  
	n = N, m = M;
	for (int i=0; i<m; i++) {
		int a, b, w;
		a = R[i][0], b = R[i][1], w = L[i];
		adj[a].push_back(make_pair(b, w));
		adj[b].push_back(make_pair(a, w));
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > proc;
	for (int i=0; i<K; i++) {
		int x = P[i];
		proc.push(make_pair(0, x));
		vis[x] = 1;
	}
	
	while (!proc.empty()) {
		
		int no = proc.top().second;
		int di = proc.top().first;
		proc.pop();
		
		if (vis[no] == 0) {
			vis[no]++;
			continue;
		}
		if (vis[no] == 2) {
			continue;
		}
		if (no == 0) {
			return di;
		}
		vis[no] = 2;
		for (int i=0; i<adj[no].size(); i++) {
			int ot = adj[no][i].first;
			int od = adj[no][i].second + di;
			if (vis[ot] == 2) continue;
			proc.push(make_pair(od, ot));
		}
		
		
	}
	
	assert(false);
	return -1;
  
}

Compilation message (stderr)

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

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