oj.uz

Submission #311244

# Submission time Handle Problem Language Result Execution time Memory
311244 2020-10-09T18:13:18 Z binary_python Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 3 ms 3840 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<int> 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(x);
			}
			else {
				if (x < q.top()) {
					q.pop();
					q.push(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(x);
			}
			else {
				if (x<q.top()) {
					q.pop();
					q.push(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][0], w = l[i];
		adj[a].push_back({w,b});
		adj[b].push_back({w,a});
	}
	for (int i=0; i<k; i++) {
		ans[i] = 0;
		d[i] = 2; 
	}
	return solve(0);	
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3840 KB Output isn't correct
2 Halted 0 ms 0 KB -