oj.uz

Submission #68048

# Submission time Handle Problem Language Result Execution time Memory
68048 2018-08-15T19:56:49 Z KieranHorgan Race (IOI11_race) C++17
0 / 100
 7 ms 4984 KB 
#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[d+v.first.first*100 + v.second])
						continue;
					done[d+v.first.first*100 + v.second] = 1;
				}
				q.push({{v.first.second, u}, {d+v.first.first, s+1}});
			}
		}
	}

	return -1;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 57.0

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