oj.uz

Submission #1003507

# Submission time Handle Problem Language Result Execution time Memory
1003507 2024-06-20T12:03:48 Z vjudge1 Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 145 ms 262144 KB 
#include "bits/stdc++.h"
#include "crocodile.h"
#define i64 long long

using namespace std;

const i64 sz = 1e5 + 5;

vector<vector<i64>> aj[sz];
i64 f[sz], s[sz];

void dfs(int v, int p = -1) {
	if (1 == (int) aj[v].size()) {
		return;
	}
	f[v] = s[v] = INT_MAX;
	for (auto& u : aj[v]) {
		int to = u[0];
		int we = u[1];
		if (to != p) {
			dfs(to, v);
			if (we + s[to] <= f[v]) {
				s[v] = f[v];
				f[v] = we + s[to];
			} else {
				s[v] = min(s[v], we + s[to]);
			}
		}
	}
}

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

	dfs(0);

	return s[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Runtime error 145 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Runtime error 145 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -