Submission #68049

#	Time	Username	Problem	Language	Result	Execution time	Memory
68049		KieranHorgan	Race (IOI11_race)	C++17	21 / 100	3051 ms	50328 KiB

race

#pragma GCC optimize("Ofast")
#include "race.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<pair<int, int>, int>> AdjList[200000];
bitset<40000000> done;

int best_path(int N, int K, int H[][2], int L[]) {
	for(int i = 0; i+1 < N; i++) {
		AdjList[H[i][0]].push_back({{L[i], H[i][1]}, i*2  });
		AdjList[H[i][1]].push_back({{L[i], H[i][0]}, i*2+1});
	}

	queue<pair<pair<int, int>, pair<int, int>>> q;
	for(int i = 0; i < N; i++)
		q.push({{i, -1}, {0, 0}});
	int u, p, d, s;
	while(!q.empty()) {
		u = q.front().first.first;
		p = q.front().first.second;
		d = q.front().second.first;
		s = q.front().second.second;
		q.pop();
		for(auto v: AdjList[u]) {
			if(v.first.second != p) {
				if(d+v.first.first > K) continue;
				if(d+v.first.first == K)
					return s+1;
				if(K <= 100) {
					if(done[v.second*100 + d+v.first.first])
						continue;
					done[v.second*100 + d+v.first.first] = 1;
				}
				q.push({{v.first.second, u}, {d+v.first.first, s+1}});
			}
		}
	}

	return -1;
}

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