Submission #3277

#	Time	Username	Problem	Language	Result	Execution time	Memory
3277		cki86201	Race (IOI11_race)	C++98	0 / 100	34 ms	27256 KiB

race

#include "race.h"
#include<string.h>

//for 21point code;

int ar[1010][1010][2];
int st[200020],en[400020],next[400020],len[400020];
int k;
const int INF = 0x7fffffff;

void addedge(int s,int d,int l,int c)
{
	next[c]=st[s];
	st[s]=c;
	en[c]=d;
	len[c]=l;
}

int Q[1010],ans=INF;
bool check[1010];

void bfs(int x)
{
	int fr=1,re=0;
	Q[0]=x;
	memset(check,0,sizeof(check));
	check[x]=1;
	while(fr!=re){
		int i;
		for(i=st[Q[re]];i;i=next[i]){
			if(check[en[i]])continue;
			Q[fr]=en[i];
			ar[x][en[i]][0]=ar[x][Q[re]][0]+1;
			ar[x][en[i]][1]=ar[x][Q[re]][1]+len[i];
			if(ar[x][en[i]][1]==k)ans=ans>ar[x][en[i]][0]?ar[x][en[i]][0]:ans;
			fr++;
		}
		re++;
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	int i;
	k=K;
	for(i=0;i<N-1;i++){
		addedge(H[i][0],H[i][1],L[i],2*i);
		addedge(H[i][1],H[i][0],L[i],2*i+1);
	}
	if(N<=1000){
		for(i=0;i<N;i++){
			bfs(i);
		}
		if(ans==INF)return -1;
		else return ans;
	}
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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