Submission #383518

#	Time	Username	Problem	Language	Result	Execution time	Memory
383518		ace_in_the_hole	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#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 main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> num_nodes >> cap;
	for (int u, v, w, i = 1; i < num_nodes; i++)
		cin >> u >> v >> w,
		adj[u].push_back(Edge(v, w)), 
		adj[v].push_back(Edge(u, w));
		
	dfs(0, -1);
	if (answer == 1e9) answer = -1;
	cout << answer;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:32:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   32 |   if (v == pa) continue; dfs(v, u);
      |   ^~
race.cpp:32:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   32 |   if (v == pa) continue; dfs(v, u);
      |                          ^~~
/tmp/cc9WKzJ6.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccx52NgB.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccx52NgB.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