Submission #400097

#	Time	Username	Problem	Language	Result	Execution time	Memory
400097		mshandilya	Race (IOI11_race)	C++14	0 / 100	318 ms	262148 KiB

race

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

using namespace std;

int best_path(int N, int K, int H[][2], int L[]) {
	std::vector<std::list<int>> adj_list(N, std::list<int> ());
	std::stack<vector<int>> alt_branch; 
	int leaf = -1, x, y, parent_x = -1, parent_y = -1, edges = 0, min_path = N+1, sum = 0;
	for(int i = 0; i<N; i++) {
		adj_list[H[i][0]].push_back(i);
		adj_list[H[i][1]].push_back(i);
	}
	for(int i = 0; i<N and leaf == -1; i++)
		if(adj_list[i].size()==1)
			leaf = i;
	x = leaf;
	if(H[adj_list[leaf].front()][1] == x)
		y = H[adj_list[leaf].front()][0];
	else
		y = H[adj_list[leaf].front()][1];
	parent_y = adj_list[leaf].front();
	sum = L[adj_list[leaf].front()];
	edges++;
	while(!alt_branch.empty() or adj_list[y].size()!=1) {
		if(sum<K) {
			if(adj_list[y].size()!=1) {
				std::list<int>::iterator i = adj_list[y].begin(), next_y;
				if(*i==parent_y)
					i++;
				next_y = i;
				if(adj_list.size()>2)
					alt_branch.push({x, y, parent_x, parent_y, sum, edges});
				parent_y = *next_y;
				if(H[*next_y][1] == y)
					y = H[*next_y][0];
				else
					y = H[*next_y][1];
				sum += L[parent_y];
				edges++;
			}
			else {
				x = alt_branch.top()[0];
				y = alt_branch.top()[1];
				parent_x = alt_branch.top()[2];
				parent_y = alt_branch.top()[3];
				sum = alt_branch.top()[4];
				edges = alt_branch.top()[5];
				std::list<int>::iterator i = adj_list[y].begin(), next_y;
				if(*i==parent_y)
					i++;
				adj_list[y].erase(i);
				i = adj_list[y].begin();
				if(*i==parent_y)
					i++;
				next_y = i;
				if(adj_list[y].size()<=2)
					alt_branch.pop();
				parent_y = *next_y;
				if(H[*next_y][1] == y)
					y = H[*next_y][0];
				else
					y = H[*next_y][1];
				sum += L[parent_y];
				edges++;
			}
		}
		else if(sum>K) {
			std::list<int>::iterator i = adj_list[x].begin(), next_x;
			if(*i==parent_x)
				++i;
			next_x = i;
			parent_x = *next_x;
			if(H[*next_x][1] == x)
				x = H[*next_x][0];
			else
				x = H[*next_x][1];
			sum -= L[parent_x];
			edges--;
		}
		else {
			min_path = min(min_path, edges);
			std::list<int>::iterator i = adj_list[x].begin(), next_x;
			if(*i==parent_x)
				++i;
			next_x = i;
			parent_x = *next_x;
			if(H[*next_x][1] == x)
				x = H[*next_x][0];
			else
				x = H[*next_x][1];
			sum -= L[parent_x];
			edges--;	
		}
	}
	if(min_path!=N+1)
		return min_path;
	else
  		return -1;
}

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