oj.uz

Submission #756610

# Submission time Handle Problem Language Result Execution time Memory
756610 2023-06-12T01:40:11 Z siewjh Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 3 ms 3284 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int inf = 1e9 + 7;
vector<pair<int, int>> adj[MAXN];
int dp[MAXN];
bool vis[MAXN], isexit[MAXN];

int dfs(int x){
	if (isexit[x]) return 0;
	if (dp[x] != -1) return dp[x];
	if (vis[x]) return inf;
	vis[x] = 1;
	vector<int> res;
	for (auto nxt : adj[x]){
		int nn = nxt.first, nd = nxt.second;
		int nres = min(dfs(nn) + nd, inf);
		res.push_back(nres);
	}
	sort(res.begin(), res.end());
	if (res.size() < 2) return dp[x] = inf;
	else return dp[x] = res[1];
}

int travel_plan(int nodes, int edges, int elist[][2], int elen[], int exits, int exarr[]){
	for (int i = 0; i < edges; i++){
		int a = elist[i][0], b = elist[i][1], d = elen[i];
		adj[a].push_back({b, d});
		adj[b].push_back({a, d});
	}
	for (int i = 0; i < exits; i++) isexit[exarr[i]] = 1;
	memset(dp, -1, sizeof(dp));
	return dfs(0);
}

Subtask #1
46.0 / 46.0

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

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 3 ms 3284 KB Output is correct
10 Incorrect 2 ms 3028 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 3 ms 3284 KB Output is correct
10 Incorrect 2 ms 3028 KB Output isn't correct
11 Halted 0 ms 0 KB -