Submission #28831

#	Time	Username	Problem	Language	Result	Execution time	Memory
28831		ozaslan	Race (IOI11_race)	C++14	21 / 100	3061 ms	17200 KiB

race

#include<bits/stdc++.h>
#include "race.h"
#define MAX_N 500000
#define oo (1<<28)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

/*static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
    freopen("grader.in.3", "r", stdin);
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}*/



vector< pair<int, int> > E[MAX_N];

typedef struct KENAR
{
	int dugum, uzunluk, derinlik;
	KENAR() {}
	KENAR(int d, int u, int de) {dugum = d, uzunluk = u, derinlik = de; }
};

int BFS(int bas, int K, int N) {

	bool kul[MAX_N];
	for (int i = 0; i < N; i++) kul[i] = 0;

	queue<KENAR> Q;
	KENAR ilk(bas, 0, 0);
	Q.push(ilk);

	while ( !Q.empty() ) {
		KENAR u = Q.front(); Q.pop();

//		if (u.uzunluk == K) return u.derinlik;
		kul[u.dugum] = 1;

		int s = E[u.dugum].size();
		for (int i = 0; i < s; i++) {
			int v = E[u.dugum][i].ff, m = E[u.dugum][i].ss;

			if (kul[v]) continue;

			if (u.uzunluk + m < K) Q.push( KENAR(v, u.uzunluk + m, u.derinlik+1) );
			if (u.uzunluk + m == K) return u.derinlik + 1;
		}
	}

	return 0;
}


int best_path(int N, int K, int H[][2], int L[])
{

	for (int i = 0; i < N-1; i++) {
		E[ H[i][0] ].push_back( make_pair( H[i][1], L[i]) );
		E[ H[i][1] ].push_back( make_pair( H[i][0], L[i]) );
	}

	int enIyi = oo, sonuc;
	for (int i = 0; i < N; i++) {
		sonuc = BFS(i, K, N);
		if (sonuc) enIyi = min(enIyi, sonuc);
	}

    if (enIyi == oo) enIyi = -1;
	return enIyi;
}

Compilation message (stderr)

race.cpp:47:1: warning: 'typedef' was ignored in this declaration
 typedef struct KENAR
 ^~~~~~~

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