oj.uz

Submission #240945

# Submission time Handle Problem Language Result Execution time Memory
240945 2020-06-21T17:35:24 Z c4ts0up Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 7 ms 640 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Incorrect 7 ms 640 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Incorrect 7 ms 640 KB Output isn't correct
10 Halted 0 ms 0 KB -