Submission #147341

#	Time	Username	Problem	Language	Result	Execution time	Memory
147341		CaroLinda	Race (IOI11_race)	C++14	9 / 100	233 ms	36800 KiB

race

#include <bits/stdc++.h>
#include "race.h"

#define lp(i,a,b) for(int i=a;i<b;i++)
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define sz size()

const int MAXN = 2e5+10 ;

using namespace std ;

int curTime ;
int ini[MAXN] , fim[MAXN] , pai[MAXN] , fatSomaVal[MAXN] , ta[MAXN] , resp[MAXN] ;
ll fatSomaKey[MAXN] , specialEdge[MAXN] ;
bool marc[MAXN] ;
vector< pair<int,ll> > adj[MAXN] ;
map<ll,int> mapa[MAXN] ;
map<ll,int>::iterator it ;

int bit[MAXN] ;
void add(int x) { for(int i = x ; i < MAXN ; i += (i&-i) ) bit[i] ++ ; }
int qry(int x)
{
	int tot = 0 ;
	for(int i = x ; i > 0 ; i -= (i&-i) )
		tot += bit[i] ;
	return tot ;
}
int get(int i , int j) { return qry(j) - qry(i) ; } 


void dfs(int x)
{
	ini[x] = ++ curTime ;

	for( pair<int,ll> p : adj[x] )
		if( ini[p.ff] == 0 )
		{
			pai[p.ff] = x ;
			dfs(p.ff) ;
			specialEdge[p.ff] = p.ss ;
		}

	fim[x] = curTime ;
}

void inserta(int idx , ll Key , int Val)
{

	if( mapa[idx].find(Key) == mapa[idx].end() )
		mapa[idx].insert(mk(Key,Val)) ;
	mapa[idx][Key] = min( mapa[idx][Key] , Val ) ;
}

int best_path(int n , int k , int h[][2] , int l[] )
{

	lp(i,0,MAXN) resp[i] = MAXN ;

	lp(i,0,n-1)
	{
		int a = h[i][0] , b = h[i][1] ;
		adj[a].pb( mk( b , 1LL * l[i] ) ) ;
		adj[b].pb( mk( a , 1LL * l[i] ) ) ;
	}


	dfs(0) ;

	queue<int> q ;

	lp(i,0,n)
		if( ini[i] == fim[i] )
		{
			marc[i] = true ;
			q.push(i) ;
			ta[i] = q.sz ;
		}

	while( !q.empty() )
	{
		int davez = q.front() ;
		q.pop() ;
		add(ini[davez]) ;

		int father = pai[davez] ;

		if( !marc[father] && get(ini[father] , fim[father]) == (fim[father]-ini[father]) )
		{
			q.push(father) ;
			marc[father] = true ;
		}

		if( ini[davez] == fim[davez] ) continue ;

		int bigChild = adj[davez][0].ff ;
		if( bigChild == pai[davez] ) bigChild = adj[davez][1].ff ;

		for(pair<int,ll> p : adj[davez])
			if( mapa[ta[bigChild]].sz < mapa[ta[p.ff]].sz && p.ff != pai[davez] )
				bigChild = p.ff ;

		fatSomaKey[davez] = fatSomaKey[bigChild] + specialEdge[bigChild] ;
		fatSomaVal[davez] = fatSomaVal[bigChild] + 1 ;
		ta[davez] = ta[bigChild] ;


		inserta( ta[davez] , specialEdge[bigChild] - fatSomaKey[davez] , 1 - fatSomaVal[davez] ) ;

		for( pair<int,ll> p : adj[davez] )
		{
			int cur = p.ff ;
			
			if( cur == bigChild || cur == pai[davez]) continue ;


			vector<pair<ll,int> > atualiza ;
			inserta( ta[cur] , -fatSomaKey[cur] , -fatSomaVal[cur] ) ;

			for(it = mapa[ta[cur]].begin() ; it != mapa[ta[cur]].end() ; it++ )
			{
				ll realKey = it->ff + fatSomaKey[cur] + specialEdge[cur] ;
				int realVal = it->ss + fatSomaVal[cur] + 1 ;
				ll updKey = realKey - fatSomaKey[davez] ;
				int updVal = realVal - fatSomaVal[davez] ;
				ll procuro = k - realKey - fatSomaKey[davez] ;

				atualiza.pb(mk(updKey , updVal)) ;

				if( mapa[ta[davez]].find(procuro) == mapa[ta[davez]].end() )
					continue ;

				resp[davez] = min(resp[davez] , mapa[ta[davez]][procuro] + fatSomaVal[davez] + realVal - 1) ;

			}

			for(pair<ll,int> p : atualiza)
				inserta(ta[davez], p.ff , p.ss ) ;

		}

		if( mapa[ta[davez]].find( k - fatSomaKey[davez] ) != mapa[ta[davez]].end() )
			resp[davez] = min(resp[davez] , mapa[ta[davez]][k-fatSomaKey[davez]] + fatSomaVal[davez]) ;


	}

	int ans = *min_element(resp, resp+n) ;

	return ans == MAXN ? -1 : ans ;

}

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