Submission #132988

#	Time	Username	Problem	Language	Result	Execution time	Memory
132988		zozder	Race (IOI11_race)	C++14	21 / 100	3018 ms	32816 KiB

race

#include "race.h"
#include <iostream>
#define maxn 2000001

using namespace std;

int map[2*maxn][3],o=0,ans=-1;
int t[maxn];

void find(int x, int k, int num)
{
	int p=x;
	while(map[p][0]!=-1)
	{
		p=map[p][0];
		if(t[map[p][1]]==0)
		{
			t[map[p][1]]=1;
			if(k-map[p][2]==0)
			{
				if(num+1<ans||ans==-1)ans=num+1;
			}
			else if(k-map[p][2]>0)find(map[p][1],k-map[p][2],num+1);
			t[map[p][1]]=0;
		}
	}
}

int best_path(int n, int K, int h[][2], int l[])
{
	for(int i=0;i<maxn;i++)
	{
		map[i][0]=-1;
		t[i]=0;
	}
	o=n-1;
	for(int i=0;i<n-1;i++)
	{
		o++;
		map[o][1]=h[i][1];
		map[o][2]=l[i];
		map[o][0]=map[h[i][0]][0];
		map[h[i][0]][0]=o;
		o++;
		map[o][1]=h[i][0];
		map[o][2]=l[i];
		map[o][0]=map[h[i][1]][0];
		map[h[i][1]][0]=o;
	}
//	for(int i=0;i<=o;i++)cout<<i<<"\t";cout<<endl;
//	for(int i=0;i<=o;i++)cout<<map[i][0]<<"\t";cout<<endl;
//	for(int i=0;i<=o;i++)cout<<map[i][1]<<"\t";cout<<endl;
	
	for(int i=0;i<n;i++)
	{
		t[i]=1;
		find(i,K,0);
		t[i]=0;
	}	
	
	return ans;
}

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