Submission #552594

#	Time	Username	Problem	Language	Result	Execution time	Memory
552594		SAAD	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	2065 ms	340 KiB

crocodile

#define F first
#define S second
#include <algorithm>
#include <math.h>
#include <vector>
#include <iostream>
using namespace std;
vector < pair < long long , long long >> x[1002];
vector <int> ex;
long long sm[1002];
bool exi[1002];
bool visa[1002];
long long dfs( int a ) {
	if (visa[a]) return 1e17;
	visa[a] = true;
	if (exi[a]) return 0;
	sm[a] = 1e17;
	for (int i = 0; i < x[a].size(); i++) {
		sm[a] = min(sm[a], dfs(x[a][i].S)+x[a][i].F);
	}
	return sm[a];
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (int i = 0; i < N; i++) {
		x[R[i][0]].push_back({ L[i],R[i][1] });
		x[R[i][1]].push_back({ L[i],R[i][0] });
	}
	for (int i = 0; i < K; i++) {
		ex.push_back(P[i]);
		exi[P[i]] = true;
	}
	dfs(0);
	bool th = true;
	int a = 0;
	long long mn = 1e18, idx = 0 , res = 0;
	while (!exi[a]) {
		th = true;
		mn = 1e18; idx = 0;
		for (int i = 0; i < x[a].size(); i++) {
			long long cst = sm[x[a][i].S] + x[a][i].F;
			if (sm[a] == cst&&th) {
				th = false;
				continue;
			}
			if (mn > cst) {
				mn = cst;
				idx = i;
			}
		}
		res += x[a][idx].F;
		a = x[a][idx].S;
		
	}
	return res;
}

Compilation message (stderr)

crocodile.cpp: In function 'long long int dfs(int)':
crocodile.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < x[a].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (int i = 0; i < x[a].size(); i++) {
      |                   ~~^~~~~~~~~~~~~

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