Submission #383539

#	Time	Username	Problem	Language	Result	Execution time	Memory
383539		ace_in_the_hole	Race (IOI11_race)	C++14	9 / 100	297 ms	52332 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 = 1e9;
const int MIN = 1005;
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 = INF, num_nodes, capa;
void minimize(int& var, const int& val) {
	if (val < var) var = val;
}

namespace Subtask2 {
	int weight[MIN][MIN], dist[MIN][MIN];
	void process() {
		for (int u = 1; u <= num_nodes; u++) {
			for (int v = 1; v <= num_nodes; v++) 
				weight[u][v] = dist[u][v] = -1;
				
			queue<int> vis_list;
			vis_list.push(u);
			weight[u][u] = dist[u][u] = 0;
			
			while (!vis_list.empty()) {
				int cur = vis_list.front(); vis_list.pop();
				if (weight[u][cur] >= capa) continue;
				for (auto edge : adj[cur]) {
					const int& nxt = edge.to;
					const int& w = edge.weight;
					if (dist[u][nxt] != -1) continue;
					dist[u][nxt] = dist[u][cur] + 1;
					weight[u][nxt] = weight[u][cur] + w;
					vis_list.push(nxt); 
				}
			}
			
			for (int v = 1; v <= num_nodes; v++)
				if (weight[u][v] == capa) minimize(answer, dist[u][v]);
		}
	}
}

namespace Subtask3 {
	int dp[MAX][105];
	
	void calc(int u, int pa) {
		dp[u][0] = 0; 
		for (int x = 1; x <= capa; x++) dp[u][x] = INF;
		
		for (auto edge : adj[u]) {
			const int& v = edge.to;
			const int& w = edge.weight;
			if (v == pa) continue; calc(v, u);
			
			for (int y = 0; y <= capa - w; y++) {
				int remain = capa - (y + w);
				if (remain >= 0)
					minimize(answer, dp[u][remain] + dp[v][y] + 2);
			}
			
			for (int y = 0; y <= capa - w; y++) 
				minimize(dp[u][w + y], dp[v][y] + 1);
		}
		minimize(answer, dp[u][capa]);
	}
	
};

void solve() {
	if (num_nodes < MIN) Subtask2 :: process(); else
	Subtask3 :: calc(0, -1);
	if (answer == INF) answer = -1;
}

int best_path(int N, int K, int H[][2], int L[]) {
	::num_nodes = N;
	::capa = 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]));
		
	solve();

	return answer;
}

Compilation message (stderr)

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

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