oj.uz

Submission #311247

# Submission time Handle Problem Language Result Execution time Memory
311247 2020-10-09T18:36:08 Z binary_python Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 5 ms 4224 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
using namespace std;

const int maxN = 100005;
const ll INF = 1e17;
vector<pair<int,int>> adj[maxN];
vector<int> d(maxN, 0);
vector<ll> ans(maxN, INF);

ll solve(int src){
	d[src] = 1;  
	priority_queue<ll> q; //The smallest two
	for (pair<int,int> v : adj[src]) {
		if (d[v.s] == 0) {
			ll x = solve(v.s); //Recursively keep going
			if (q.size() < 2) {
				q.push(v.f+x);
			}
			else {
				if (v.f+x < q.top()) {
					q.pop();
					q.push(v.f+x);
				}
			}
		}
		else if (d[v.s] == 1) { //Don't want to backtrack
			continue; 
		}
		else { //We already processed it
			ll x = ans[v.s];
			if (q.size() < 2) {
				q.push(v.f+x);
			}
			else {
				if (v.f+x<q.top()) {
					q.pop();
					q.push(v.f+x);
				}
			}
		}
	}
	if (q.size() < 2) ans[src] = INF;
	else ans[src] = q.top();
	d[src] = 2; 
	return ans[src];
}


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], b = r[i][1], w = l[i];
		adj[a].push_back({w,b});
		adj[b].push_back({w,a});
	}
	for (int i=0; i<k; i++) {
		ans[p[i]] = 0;
		d[p[i]]= 2; 
	}
	return solve(0);	
}

Subtask #1
46.0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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