Submission #132496

#	Time	Username	Problem	Language	Result	Execution time	Memory
132496		socho	Race (IOI11_race)	C++14	21 / 100	3019 ms	12208 KiB

race

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

int n, targ;
vector<pair<int, int> > adj[200005]; // other, dist
bool vis[200005];
pair<int, int> dstore[200005];

void dfs(int node, int dist, int paths) {
	// dist: current distance, paths: num paths
	vis[node] = true;
	for (int i=0; i<adj[node].size(); i++) {
		int cons = adj[node][i].first;
		if (!vis[cons]) {
			dfs(cons, dist+adj[node][i].second, paths+1);
		}
	}
	dstore[node] = make_pair(dist, paths);
}

int getbest(int s) {
	memset(vis, 0, sizeof vis);
	dfs(s, 0, 0);
	int best = INT_MAX;
	bool can = false;
	for (int i=0; i<n; i++) {
		if (dstore[i].first == targ) {
			can = true;
			best = min(best, dstore[i].second);
		}
	}
	if (best == INT_MAX) return -1;
	return best;
}

int best_path(int N, int K, int H[][2], int L[]) {
	n = N;
	targ = K;
	for (int i=0; i<n-1; i++) {
		int a = H[i][0];
		int b = H[i][1];
		int l = L[i];
		adj[a].push_back(make_pair(b, l));
		adj[b].push_back(make_pair(a, l));
	}
	bool can = false;
	int best = INT_MAX;
	for (int source = 0; source < N; source++) {
		int res = getbest(source);
		if (res != -1) {
			can = true;
			best = min(best, res);
		}
	}
	if (!can) return -1;
	return best;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, int)':
race.cpp:13:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<adj[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~
race.cpp: In function 'int getbest(int)':
race.cpp:26:7: warning: variable 'can' set but not used [-Wunused-but-set-variable]
  bool can = false;
       ^~~

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