Submission #383530

#	Time	Username	Problem	Language	Result	Execution time	Memory
383530		ace_in_the_hole	Race (IOI11_race)	C++14	0 / 100	12 ms	14828 KiB

race

#include "race.h"

#include<bits/stdc++.h>
using namespace std;

#define push_back emplace_back

typedef long long Int;
typedef long double Real;

const int MOD = 2004010501;//>2e9
const Int INF = 1e18;

const int MAX = 2e5 + 500;
struct Edge {
	int to, weight;
	Edge(int to, int weight) : to(to), weight(weight) {}
};
vector<Edge> adj[MAX];

int answer = 1e9, num_nodes, cap;

//values shifted by 1 : avoid '0', '0' means oo
void minimize(int& var, const int& val) {
	if (var == 0 or val < var) var = val;
}
map<int,int> dp[MAX]; 

void dfs(int u, int pa) {
	dp[u][0] = 1; //means '0'
	for (auto edge : adj[u]) {
		const int& v = edge.to;
		const int& w = edge.weight;
		if (v == pa) continue; dfs(v, u);
		
		for (auto path : dp[v]) {
			int branch = cap - (path.first + w);
			if (branch >= 0 and dp[u][branch] > 0 and path.second > 0)
				answer = min(answer, dp[u][branch] + path.second);
		}
		
		for (auto path : dp[v]) 
			if (path.second > 0 and w + path.first <= cap) 
				minimize(dp[u][w + path.first], path.second + 1);
	}
	if (dp[u][cap] > 0)
		answer = min(answer, dp[u][cap] - 1);
//	cerr << "Node " << u << '\n';
//	for (auto path : dp[u]) cerr << ' ' << path.first << ':' << path.second << '\n'; 
}

int best_path(int N, int K, int H[][2], int L[]) {
	num_nodes = N;
	cap = K;
	for (int i = 0; i < N; i++) 
		adj[H[i][0]].push_back(Edge(H[i][1], L[i])),
		adj[H[i][1]].push_back(Edge(H[i][0], L[i]));
	dfs(0, -1);
	if (answer == 1e9) answer = -1;
	return answer;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:34:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   34 |   if (v == pa) continue; dfs(v, u);
      |   ^~
race.cpp:34:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   34 |   if (v == pa) continue; dfs(v, u);
      |                          ^~~

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