oj.uz

Submission #3268

# Submission time Handle Problem Language Result Execution time Memory
3268 2013-08-30T01:49:29 Z cki86201 Race (IOI11_race) C++
0 / 100
 40 ms 27480 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 27480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 27480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 27480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 27480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -