Submission #311246

#	Time	Username	Problem	Language	Result	Execution time	Memory
311246		binary_python	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	5 ms	4224 KiB

crocodile

#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(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 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11