Submission #383524

#	Time	Username	Problem	Language	Result	Execution time	Memory
383524		ace_in_the_hole	Race (IOI11_race)	C++14	Compilation error	0 ms	0 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 u, v, w, i = 1; i < n; i++) 
		adj[u].push_back(Edge(v, w)),
		adj[v].push_back(Edge(u, w));
	dfs(0, -1);
	cout << 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);
      |                          ^~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int)':
race.cpp:60:1: warning: no return statement in function returning non-void [-Wreturn-type]
   60 | }
      | ^
race.cpp:55:11: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |  for (int u, v, w, i = 1; i < n; i++)
      |           ^
race.cpp:55:14: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |  for (int u, v, w, i = 1; i < n; i++)
      |              ^
race.cpp:17:50: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |  Edge(int to, int weight) : to(to), weight(weight) {}
      |                                                  ^
race.cpp:55:17: note: 'w' was declared here
   55 |  for (int u, v, w, i = 1; i < n; i++)
      |                 ^
/tmp/ccHT1ECz.o: In function `main':
grader.cpp:(.text.startup+0x24): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status