| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 245214 | A02 | Race (IOI11_race) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "race.h"
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
void root_tree (vector<int> &parents, vector<vector<pair<int, int> > > &adjacent, int current){
for (int i = 0; i < adjacent[current].size(); i++){
long long child = adjacent[current][i].first;
if (parents[child] == -1){
parents[child] = current;
root_tree(parents, adjacent, child);
}
}
}
void process_node(int N, vector<int> &parents, vector<vector<pair<int, int> > > &adjacent, vector<vector<int> > &least_highways, int current){
least_highways[current][0] = 0;
for (int i = 0; i < adjacent[current].size(); i++){
int child = adjacent[current][i].first;
int d = adjacent[current][i].second;
if (parents[child] == current){
if (least_highways[child][0] == N + 1){
process_node(N, parents, adjacent, least_highways, child);
}
for (int r = d; r < least_highways[0].size(); r++){
//cout << r << ' ' << d << ' ' << 'c' << child << ' ' << current << ' ' << least_highways[child][r - d] << endl;
if (r - d >= 0){
least_highways[current][r] = min(least_highways[current][r], least_highways[child][r - d] + 1);
}
}
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pair<int, long long> > > adjacent (N, vector<pair<int, long long> >());
for (int i = 0; i < N - 1; i++){
adjacent[H[i][0]].push_back(make_pair(H[i][1], L[i]));
adjacent[H[i][1]].push_back(make_pair(H[i][0], L[i]));
}
if (N <= 1000){
long long best = N + 1;
for (int i = 0; i < N; i++){
//cout << i << ' ' << endl;
vector<pair<long long, long long> > distance (N, make_pair(-1, -1));
queue<long long> to_visit;
to_visit.push(i);
distance[i].first = 0;
distance[i].second = 0;
while (!to_visit.empty()){
long long current = to_visit.front();
to_visit.pop();
if (distance[current].second == K){
best = min(best, distance[current].first);
}
for (int r = 0; r < adjacent[current].size(); r++){
long long next = adjacent[current][r].first;
if (distance[next].first == -1){
distance[next].first = distance[current].first + 1;
distance[next].second = distance[current].second + adjacent[current][r].second;
to_visit.push(next);
}
}
}
}
if (best == N + 1){
return -1;
}
return best;
} else {
vector<int> parents (N, -1);
parents[0] = -2;
root_tree(parents, adjacent, 0);
vector<vector<int> > least_highways (N, vector<int> (K + 1, N + 1));
process_node(N, parents, adjacent, least_highways, 0);
int best = N + 1;
// for (int i = 0; i < N; i ++){
//
// cout << endl;
// cout << i << ":" << endl;
// for (int j = 0; j <= K; j++){
// cout << least_highways[i][j] << ' ';
// }
// cout << endl;
//
// }
for (int n = 0; n < N; n++){
for (int i = 0; i < adjacent[n].size(); i++){
int child1 = adjacent[n][i].first;
if (parents[child1] == n){
for (int j = i + 1; j < adjacent[n].size(); j++){
int child2 = adjacent[n][j].first;
if (parents[child2] == n){
int added_distance = adjacent[n][i].second + adjacent[n][j].second;
for (int r = 0; r <= K - added_distance; r++){
best = min(best, 2 + least_highways[child1][r] + least_highways[child2][K - added_distance - r]);
}
}
}
}
best = min (best, least_highways[n][K]);
//cout << n << ' ' << best << endl;
}
}
if (best > N){
return -1;
}
return best;
return N;
}
}