Submission #13481

#	Time	Username	Problem	Language	Result	Execution time	Memory
13481		ainta	Race (IOI11_race)	C++98	100 / 100	680 ms	33632 KiB

race

#include "race.h"
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[201000], Len[201000];
int n, LL, Res, D[201000], Dep[201000], C[201000], Q[201000], par[201000];
bool chk[201000];

int BFS(int a){
	int h = 0, t = 0, x, i;
	Q[++t] = a;
	par[t] = D[t] = Dep[t] = 0, C[t] = 1;
	while (h < t){
		x = Q[++h];
		for (i = 0; i < E[x].size(); i++){
			if (!chk[E[x][i]] && Q[par[h]] != E[x][i]){
				Q[++t] = E[x][i];
				par[t] = h, D[t] = D[h] + Len[x][i], Dep[t] = Dep[h] + 1, C[t] = 1;
			}
		}
	}
	for (i = t; i>1; i--)C[par[i]] += C[i];
	return t;
}

int get_mid(int SZ){
	int i, M = SZ + 1, x;
	for (i = 1; i <= SZ; i++){
		if (M > C[i] && C[i] > SZ / 2)M = C[i], x = Q[i];
	}
	return x;
}

int w[1010000], Li[201000];
void Do(int a){
	int SZ = BFS(a);
	if (SZ == 1)return;
	int m = get_mid(SZ), i, j, cnt = 0;
	chk[m] = true;
	for (i = 0; i < E[m].size(); i++){
		if (!chk[E[m][i]])Do(E[m][i]);
	}
	for (i = 0; i < E[m].size(); i++){
		if (chk[E[m][i]])continue;
		SZ = BFS(E[m][i]);
		for (j = 1; j <= SZ; j++){
			D[j]+= Len[m][i], Dep[j]++;
			if (D[j]>LL)continue;
			if (D[j] == LL)Res = min(Res, Dep[j]);
			else if (w[LL - D[j]])Res = min(Res, Dep[j] + w[LL - D[j]]);
		}
		for (j = 1; j <= SZ; j++){
			if (D[j] <= LL && (w[D[j]] == 0 || w[D[j]] > Dep[j]))w[D[j]] = Dep[j], Li[cnt++] = D[j];
		}
	}
	chk[m] = false;
	for (i = 0; i < cnt; i++)w[Li[i]] = 0;
}

int best_path(int N, int K, int H[][2], int L[])
{
	int i;
	n = N, LL = K;
	for (i = 0; i < n - 1; i++){
		E[H[i][0]].push_back(H[i][1]);
		E[H[i][1]].push_back(H[i][0]);
		Len[H[i][0]].push_back(L[i]);
		Len[H[i][1]].push_back(L[i]);
	}
	Res = n + 1;
	Do(0);
	return Res == n + 1 ? -1 : Res;
}

Compilation message (stderr)

race.cpp: In function 'int BFS(int)':
race.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i < E[x].size(); i++){
               ~~^~~~~~~~~~~~~
race.cpp: In function 'void Do(int)':
race.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[m].size(); i++){
              ~~^~~~~~~~~~~~~
race.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[m].size(); i++){
              ~~^~~~~~~~~~~~~
race.cpp: In function 'int get_mid(int)':
race.cpp:32:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return x;
         ^
race.cpp: In function 'void Do(int)':
race.cpp:28:21: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int i, M = SZ + 1, x;
                     ^

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