Submission #211313

#	Time	Username	Problem	Language	Result	Execution time	Memory
211313		socho	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	6 ms	2688 KiB

crocodile

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

#include "crocodile.h"

int n, m;
const int MXN = 100005;
vector<pair<int, int> > adj[MXN];
bool ter[MXN];
int dist[MXN];
int via[MXN];

int best() {
	int dis[MXN];
	for (int i=0; i<n; i++) dis[i] = INT_MAX;
	dis[0] = 0;
	priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > src;
	src.push(make_pair(0, make_pair(0, -1)));
	while (!src.empty()) {
		int di = src.top().first;
		int no = src.top().second.first;
		// int fr = src.top().second.second;
		src.pop();
		
		if (dis[no] < di) continue;
		dis[no] = di;
		
		for (int i=0; i<adj[no].size(); i++) {
			int ot = adj[no][i].first;
			int od = adj[no][i].second;
			if (ot == via[no]) continue; // cant take optimal
			if (dis[ot] > od + di) {
				dis[ot] = od + di;
				src.push(make_pair(dis[ot], make_pair(ot, no)));
			}
		}
	}
	int be = INT_MAX;
	for (int i=0; i<n; i++) {
		if (ter[i]) be = min(be, dis[i]);
	}
	return be;
}

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++) {
		adj[R[i][0]].push_back(make_pair(R[i][1], L[i]));
		adj[R[i][1]].push_back(make_pair(R[i][0], L[i]));
	}
	
	
	for (int i=0; i<n; i++) dist[i] = INT_MAX, via[i] = INT_MAX;
	
	priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > src;
	
	int p = K;
	for (int i=0; i<p; i++) {
		int x = P[i];
		ter[x] = true;
		dist[x] = 0;
		src.push(make_pair(0, make_pair(x, -1)));
	}
	
	while (!src.empty()) {
		
		int di = src.top().first;
		int no = src.top().second.first;
		int fr = src.top().second.second;
		src.pop();
		
		if (dist[no] < di) continue;
		dist[no] = di;
		via[no] = fr;
		
		for (int i=0; i<adj[no].size(); i++) {
			int on = adj[no][i].first;
			int od = adj[no][i].second;
			if (dist[on] > di + od) {
				dist[on] = di + od;
				src.push(make_pair(dist[on], make_pair(on, no)));
			}
		}
		
	}
	
  return N;
}

Compilation message (stderr)

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

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