oj.uz

Submission #132976

# Submission time Handle Problem Language Result Execution time Memory
132976 2019-07-20T03:22:04 Z zozder Race (IOI11_race) C++14
0 / 100
 5 ms 3448 KB 
#include "race.h"
#include <iostream>
#define maxn 200001

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++)find(i,K,0);
	
	return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Incorrect 5 ms 3448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Incorrect 5 ms 3448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Incorrect 5 ms 3448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Incorrect 5 ms 3448 KB Output isn't correct
4 Halted 0 ms 0 KB -