Submission #915030

#	Time	Username	Problem	Language	Result	Execution time	Memory
915030		Cabralbonzao	Race (IOI11_race)	C++17	43 / 100	3039 ms	181284 KiB

race

#include <bits/stdc++.h>
//#include "race.h"
using namespace std;

#define N 200002
#define INF 1000000020
#define INFLL 1000000000000000020
#define fi first
#define se second
#define pb push_back
#define LOG 18
#define SQRT 25

typedef long int ll; 
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef vector< ll > vl;
typedef vector< pll > vll;
typedef tuple< int, int, int> tiii;
typedef tuple< ll, ll, ll> tlll;

vector<ll>*vet[N];
ll ans=N;
ll k;
ll sz[N];
ll lvl[N];
ll sum[N];
vector<ll>grafo[N];
map<pll,ll>qtd;
map<pll,ll> :: iterator it;
map<pll,ll>peso;
map<ll,bool>has;

void Verify(ll val)
{
	if(!has[val])
	{
		has[val]=true;
		qtd[{val,INFLL}]++;
	}
	return;
}

void ADD(ll val,ll nivel)
{
	Verify(val);
	qtd[{val,nivel}]++;
	return;
}

void REMOVE(ll val,ll nivel)
{
	qtd[{val,nivel}]--;
	if(!qtd[{val,nivel}])
	{
		qtd.erase({val,nivel});
	}
	return;
}

void build(ll u,ll p)
{
	sz[u]=1;
	ll w;
	for(auto v : grafo[u])
	{
		if(v==p)
			continue;
		w=peso[{u,v}];
		lvl[v]=lvl[u]+1LL;
		sum[v]=sum[u]+w;
		build(v,u);
		sz[u]+=sz[v];
	}
	return;
}

void DFS(ll u,ll p,bool keep)
{
	ll mx=-1,big;
	for(auto v : grafo[u])
	{
		if(v==p)
			continue;
		if(mx<sz[v])
		{
			mx=sz[v];
			big=v;
		}
	}
	for(auto v : grafo[u])
	{
		if(v==p || v==big)
			continue;
		DFS(v,u,false);
	}
	if(mx!=-1)
	{
		DFS(big,u,true);
		vet[u]=vet[big];
	}else
	{
		vet[u]=new vector<ll>();
	}
	ll K=k+2*sum[u];
	(*vet[u]).pb(u);
	ADD(sum[u],lvl[u]);
	for(auto v : grafo[u])
	{
		if(v==p || v==big)
			continue;
		for(auto x : (*vet[v]))
		{
			Verify(K-sum[x]);
			it=qtd.lower_bound({K-sum[x],0LL});
			ans=min(ans,lvl[x]+
					(*it).first.second-
					2*lvl[u]);
		}
		for(auto x : (*vet[v]))
		{
			(*vet[u]).pb(x);
			ADD(sum[x],lvl[x]);
		}
	}
	Verify(k+sum[u]);
	it=qtd.lower_bound({k+sum[u],0LL});
	ans=min(ans,(*it).first.second-lvl[u]);
	if(!keep)
	{
		for(auto x : (*vet[u]))
		{
			REMOVE(sum[x],lvl[x]);
		}
	}
	return;
}

int best_path(int n, int K, int H[][2], int L[])
{
	ll i=0,u,v,w;
	k=K;
	while(i<n-1)
	{
		u=H[i][0];
		v=H[i][1];
		grafo[u].pb(v);
		grafo[v].pb(u);
		peso[{u,v}]=peso[{v,u}]=L[i];
		i++;
	}
	lvl[0]=1;
	build(0,0);
	DFS(0,0,true);
	if(ans>n)
		ans=-1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:141:13: warning: unused variable 'w' [-Wunused-variable]
  141 |  ll i=0,u,v,w;
      |             ^
race.cpp: In function 'void DFS(ll, ll, bool)':
race.cpp:110:15: warning: 'big' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |   if(v==p || v==big)
      |              ~^~~~~

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