Submission #67998

#	Time	Username	Problem	Language	Result	Execution time	Memory
67998		KieranHorgan	Race (IOI11_race)	C++17	21 / 100	3074 ms	69700 KiB

race

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

vector<pair<int, int>> AdjList[200000];
bitset<200000> visited1[100];
bitset<200000> visited2[100];
int prv[100][200000];

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]});
		AdjList[H[i][1]].push_back({L[i], H[i][0]});
	}

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

	return -1;
}

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