Submission #132934

#	Time	Username	Problem	Language	Result	Execution time	Memory
132934		Boxworld	Race (IOI11_race)	C++14	21 / 100	3028 ms	6392 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN=200100;
struct edge{int v,d,nxt;}a[maxN*2];
int k,tmp=0,ans=-1,head[maxN],vis[maxN];
void add(int u,int v,int d){
	a[tmp].v=v;a[tmp].d=d;a[tmp].nxt=head[u];head[u]=tmp++;
}
void dfs(int u,int s,int ed){
	vis[u]=1;
//	printf("to->%d dis:%d vis_edge:%d\n",u,s,ed);
	if(s==k){
		if(ed<ans||ans==-1)ans=ed;
		return;
	}
	for (int i=head[u];i!=-1;i=a[i].nxt){
		int v=a[i].v,d=a[i].d;
		if (vis[v])continue;
		if(s+d<=k)dfs(v,s+d,ed+1);
	}
}
int best_path(int N, int K, int H[][2], int L[]){
	k=K;
	for (int i=0;i<N;i++)head[i]=-1;
	for (int i=0;i<N-1;i++){
		add(H[i][0],H[i][1],L[i]);
		add(H[i][1],H[i][0],L[i]);
	}
	for (int i=0;i<N;i++){
		memset(vis,0,sizeof(vis));
		dfs(i,0,0);
	}
	return ans;
}

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