Submission #147178

#	Time	Username	Problem	Language	Result	Execution time	Memory
147178		CaroLinda	Race (IOI11_race)	C++14	0 / 100	16 ms	15224 KiB

race

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

#define lp(i,a,b) for(int i=a;i<b;i++)
#define ll int
#define pii pair<int,int>
#define ff first
#define ss second
#define mk make_pair
#define pb push_back
#define sz size()
#define mip map<int,int>::iterator

const int MAXN = 2e5+10 ;

using namespace std ;

int curTime ;
int  fatSomaVal[MAXN] ;
int ini[MAXN] , fim[MAXN] , bit[MAXN] , qual[MAXN] , pai[MAXN] , resp[MAXN] ;
int fatSomaKey[MAXN] , specialEdge[MAXN] ;
vector<pair<int,int> > adj[MAXN] ;
map<int , int > mapa[MAXN] ;
bool marc[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 realKey(int i , int x) { return x + fatSomaKey[i] + specialEdge[i] ; }
int realVal(int i , int x) { return mapa[qual[i]][x] + fatSomaVal[i] ; }

void dfs(int x)
{
	ini[x] = ++curTime ;
	for(pii i : adj[x])
		if(ini[i.ff] == 0)
		{
			dfs(i.ff) ;
			pai[i.ff] = x;
			specialEdge[i.ff] = i.ss ;
		}
	fim[x] = curTime ;
}


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

	memset(resp, -1, sizeof resp) ;

	lp(i,0,N-1)
	{
		int a = H[i][0] , b = H[i][1] ;
		adj[a].pb(mk(b , L[i])) ;
		adj[b].pb(mk(a,L[i])) ;
	}
	dfs(0) ;

	queue<int> q ;

	lp(i,0,N)
		if(ini[i] == fim[i])
		{
			q.push(i) ;
			marc[i] = true ;
			qual[i] = q.sz ;
			mapa[q.sz].insert(mk(0,0)) ;
		}

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

		add(ini[davez]) ;

		if( !marc[pai[davez]] && (qry(fim[pai[davez]]) - qry(ini[pai[davez]])) == (fim[pai[davez]]-ini[pai[davez]]) )
		{
			marc[pai[davez]] = true ;
			q.push(pai[davez]) ;
		}

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

		pii bigChild = mk( mapa[qual[adj[davez][0].ff]].sz , 0 ) ;

		for(pii p : adj[davez])
			bigChild = max( bigChild , pii( 1*mapa[qual[p.ff]].sz , p.ff ) ) ;

		fatSomaKey[davez] = fatSomaKey[ bigChild.ss ] + specialEdge[bigChild.ss] ;
		fatSomaVal[davez] = fatSomaVal[bigChild.ss] + 1 ;
		qual[davez] = qual[bigChild.ss] ;

		if( mapa[qual[davez]].find( K - fatSomaKey[davez] ) != mapa[qual[davez]].end() )
			resp[davez] = mapa[qual[davez]][K-fatSomaKey[davez]] + fatSomaVal[davez] ;

		lp(i,0,adj[davez].size())
		{
			int cur = adj[davez][i].ff ;

			if(cur == bigChild.ss) continue ;

			vector<pii> atualiza ;

			for(mip it = mapa[qual[cur]].begin() ; it != mapa[qual[cur]].end() ; it++ )
			{
				int realX = realKey(cur , it->ff) ;
				int realY = realVal(cur , it->ff) + 1 ;
				int vaiUpdtarX = realX - fatSomaKey[davez] ;
				int vaiUpdtarY = realY - fatSomaVal[davez] ;
				int procuro = K - realX - fatSomaKey[davez] ;

				atualiza.pb(mk(vaiUpdtarX, vaiUpdtarY)) ;

				if( K == realX ) resp[davez] = max(resp[davez] , realY) ;
				if( mapa[qual[davez]].find( procuro ) == mapa[qual[davez]].end() ) continue ;

				resp[davez] = max(resp[davez], mapa[qual[davez]][procuro] + fatSomaVal[davez] + realY - 1 ) ;

			}

			for(pii p : atualiza) 
			{
				if(mapa[qual[davez]].find(p.ff) == mapa[qual[davez]].end())
					mapa[qual[davez]].insert(p) ;
				mapa[qual[davez]][p.ff] = max( mapa[qual[davez]][p.ff] , p.ss ) ;
			}

		}

	}

	return *max_element(resp,resp+N) ;

}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:4:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
race.cpp:104:6:
   lp(i,0,adj[davez].size())
      ~~~~~~~~~~~~~~~~~~~~~      
race.cpp:104:3: note: in expansion of macro 'lp'
   lp(i,0,adj[davez].size())
   ^~

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