oj.uz

Submission #123594

# Submission time Handle Problem Language Result Execution time Memory
123594 2019-07-01T17:58:26 Z johutha Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 4 ms 760 KB 
#include "crocodile.h"
#include <vector>

using namespace std;

vector<int> vals;

vector<vector<pair<int,int>>> adjlist;

int dfs(int curr, int prev)
{
	if (vals[curr] != -1) return vals[curr];
	vals[curr] = 1e9;
	int fr = 1e9;
	int sec = 1e9;

	for (auto p : adjlist[curr])
	{
		int next = p.first;
		if (next == prev) continue;
		int val = dfs(next, curr) + p.second;
		if (val <= fr)
		{
			sec = fr;
			fr = val;
		}
		else if (val <= sec)
		{
			sec = val;
		}
	}

	return vals[curr] = sec;
}

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[])
{
	vals.resize(n, -1);
	for (int i = 0; i < k; i++)
	{
		vals[P[i]] = 0;
	}
	adjlist.resize(n);
	for (int i = 0; i < m; i++)
	{
		adjlist[R[i][0]].push_back({R[i][1], L[i]});
		adjlist[R[i][1]].push_back({R[i][0], L[i]});
	}
	return dfs(0, -1);
}

Subtask #1
46.0 / 46.0

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

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Incorrect 2 ms 380 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 252 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Incorrect 2 ms 380 KB Output isn't correct
11 Halted 0 ms 0 KB -