Submission #807304

#	Time	Username	Problem	Language	Result	Execution time	Memory
807304		SteGG	Race (IOI11_race)	C++17	21 / 100	3058 ms	28760 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

const int maxn = 1e6 + 5;
const int inf = 1e9 + 7;

int depth[maxn];
int road[maxn];
int n, k;
vector<pair<int, int>> tr[maxn];

struct Node{
	int index, depth, road;
	int parent;
	Node(){}

	Node(int _index, int _depth, int _road, int _parent) : index(_index), depth(_depth), road(_road), parent(_parent) {}

	bool operator>(const Node &other) const{
		if(depth != other.depth) return depth > other.depth;
		else if(road != other.road){
			if(road <= k && other.road <= k) return road < other.road;
			else if(road <= k) return false;
			else if(other.road <= k) return true;
			else return road > other.road;
		}

		return index > other.index;
	}
};

void dfs(int u, int p){
	for(auto node : tr[u]){
		int v = node.first;
		int w = node.second;
		if(v == p) continue;
		depth[v] = depth[u] + 1;
		road[v] = road[u] + w;
		dfs(v, u);
	}
}

int bfs(int u){
	priority_queue<Node, vector<Node>, greater<Node>> q;
	q.push({u, 0, 0, -1});
	while(!q.empty()){
		Node first = q.top();
		q.pop();
		int u = first.index;
		int cur = first.road;
		if(cur == k){
			return first.depth;
		}else if(cur > k) continue;

		for(auto node : tr[u]){
			int v = node.first;
			int w = node.second;
			if(v == first.parent) continue;
			q.push({v, first.depth + 1, cur + w, u});
		}
	}

	return inf;
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	for(int i = 0; i < n - 1; i++){
		int a, b, l;
		a = H[i][0];
		b = H[i][1];
		l = L[i];
		tr[a].push_back({b, l});
		tr[b].push_back({a, l});
	}

	int result = inf;
	if(k <= 100){
		for(int i = 0; i < n; i++){
			int temp = bfs(i);
			result = min(result, temp);
		}
	}else{
		for(int i = 0; i < n; i++){
			depth[i] = 0;
			road[i] = 0;
			dfs(i, -1);
			for(int j = 0; j < n; j++){
				if(road[j] == k && result > depth[j]){
					result = depth[j];
				}
			}
		}
	}

	if(result == inf){
		return -1;
	}else{
		return result;
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57