제출 #240945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240945		c4ts0up	악어의 지하 도시 (IOI11_crocodile)	C++17	46 / 100	7 ms	640 KiB

crocodile

#include "crocodile.h"
#define pb push_back
#define ll long long
#define ff first
#define ss second
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 2000;
const int INF = 1e9;

unordered_set <int> vis;
vector <pair <int,int> > Adj[NMAX];
unordered_set <int> salidas;

bool IsExit(int x) {
	return salidas.count(x);
}

// Devuelve la salida mas cercana a o
int DFS(int o) {
	// lo visito
	vis.insert(o);

	//cerr << "Visitando el nodo " << o << endl;

	int primera = INF, segunda = INF;
	// es nodo salida
	if (IsExit(o)) return 0;

	// es nodo padre
	for (pair <int,int> p : Adj[o]) {
		// es el padre, ya lo visitamos
		if (vis.count(p.ff)) continue;
		// es visitable
		else {
			int res = DFS(p.ff) + p.ss;

			if (res <= primera) segunda = primera, primera = res;
			else if (res <= segunda) segunda = res;
		}
	}

	//cerr << "1a: " << primera << ", 2a: " << segunda << endl;
	return segunda;
}


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int i=0; i<M; i++) {
		Adj[R[i][0]].pb({R[i][1], L[i]});
		Adj[R[i][1]].pb({R[i][0], L[i]});
	}

	/*
	for (int i=0; i<N; i++) {
        cerr << i << " : ";
        for (pair <int,int> x : Adj[i]) cerr << "(" << x.ff << ", " << x.ss << "), ";
        cerr << endl;
	}
	*/

	for (int i=0; i<K; i++) salidas.insert(P[i]);

	return DFS(0);
}

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