Submission #157149

#	Time	Username	Problem	Language	Result	Execution time	Memory
157149		GioChkhaidze	Race (IOI11_race)	C++14	100 / 100	959 ms	38776 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define F first
#define S second

using namespace std;

const int Nm=200005;
const int Mm=1000006;

int n,k,ANS=1e9,Lvl[Nm],F[Mm],F1[Mm];
pair < int , int > val;
vector < pair < int , int > > v[Nm];

int Dfs (int x,int size,int &Center,int p) {
	int tot=1;
	for (int i=0; i<v[x].size(); i++)
		if (Lvl[v[x][i].F]==-1 && v[x][i].F!=p) tot+=Dfs(v[x][i].F,size,Center,x);
	if (Center==-1 && (2*tot>=size || p==-1)) Center=x;
	return tot;
}

void Df(int x,int p,int type) {
	if (val.F==k) ANS=min(ANS,val.S);
	if (val.F>=k) return ;

	if (type==1) F[val.F]=min(F[val.F],val.S),ANS=min(ANS,F[val.F]+F1[k-val.F]);
		else 
	if (type==2) F1[val.F]=min(F1[val.F],F[val.F]),F[val.F]=1e9;
		else F1[val.F]=1e9;	
		
	for (int i=0; i<v[x].size(); i++) {
		if (Lvl[v[x][i].F]==-1 && v[x][i].F!=p) {
			val.F+=v[x][i].S,val.S++;
			Df(v[x][i].F,x,type);
			val.F-=v[x][i].S,val.S--;
		}
	}
}

void Build(int x,int size,int depth) {
	int Center=-1;
	Dfs(x,size,Center,-1);
	
	Lvl[Center]=depth;
	for (int i=0; i<v[Center].size(); i++)
		if (Lvl[v[Center][i].F]==-1) {
			val.F=v[Center][i].S,val.S=1;
			Df(v[Center][i].F,Center,1);
			Df(v[Center][i].F,Center,2);
			val.F=0,val.S=0;
		}
		
	Df(Center,-1,3);
	
	for (int i=0; i<v[Center].size(); i++)
		if (Lvl[v[Center][i].F]==-1) Build(v[Center][i].F,size/2,depth+1);
}


int best_path(int N, int K, int H[][2], int L[])
{
	n=N,k=K;
	
	for (int i=0; i<n-1; i++) {
		v[H[i][0]].push_back({H[i][1],L[i]});
		v[H[i][1]].push_back({H[i][0],L[i]});
	}
	
	for (int i=0; i<n; i++)
		Lvl[i]=-1;
	
	for (int i=1; i<=k; i++)
		F1[i]=1e9,F[i]=1e9;
	Build(1,n,0);
	
	if (ANS==1e9) ANS=-1;

  	return ANS;
}

Compilation message (stderr)

race.cpp: In function 'int Dfs(int, int, int&, int)':
race.cpp:17:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x].size(); i++)
                ~^~~~~~~~~~~~
race.cpp: In function 'void Df(int, int, int)':
race.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[x].size(); i++) {
                ~^~~~~~~~~~~~
race.cpp: In function 'void Build(int, int, int)':
race.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[Center].size(); i++)
                ~^~~~~~~~~~~~~~~~~
race.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v[Center].size(); i++)
                ~^~~~~~~~~~~~~~~~~

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