Submission #151928

#	Time	Username	Problem	Language	Result	Execution time	Memory
151928		CaroLinda	Rail (IOI14_rail)	C++14	0 / 100	385 ms	54520 KiB

rail

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

#define printPii(p) printf("%d %d\n" , p.ff , p.ss )
#define lp(i,a,b) for(int i = a ;i<b;i++)
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define sz size()
#define mk make_pair

const int MAXN = 5e3+10 ;
const int inf = 1e9+10 ;

using namespace std ;

int n ;
int ini[2] , idx[2] ;
int m[MAXN][MAXN] ;
bool marc[MAXN] ;
vector<int> jaFoi[2] ;
vector<pii> dist[2] ;

void findDistance(int source, int whereToSave, bool yes)
{
	marc[source] = true ;

	lp(i,0,n)
		if(!marc[i])
		{
			m[source][i] = getDistance(source, i) ;
			if(yes)
			dist[whereToSave].pb( { m[source][i] , i } ) ;
		}

	if(yes)
	sort( dist[whereToSave].begin() , dist[whereToSave].end() ) ;
}

void findLocation(int N, int first, int location[], int stype[])
{

	n = N ;
	location[0] = first , stype[0] = 1 ;

	if(n==1) return ;

	findDistance(0,0,1);
	
	ini[1] = dist[0][0].ss ;

	findDistance(ini[1],1,1);
	
	dist[0].resize(0) ;
	ini[0] = dist[1][0].ss ;

	findDistance(ini[0],0,1);

	location[ini[1]] = first + m[0][ini[1]] ;
	location[ini[0]] = location[ini[1]] - m[ini[1]][ini[0]] ;
	stype[ini[1]] = 2 ;
	stype[ini[0]] = 1 ;
	lp(i,0,2) dist[i].pb({inf,inf}) ;
	jaFoi[1].pb(ini[0]) ;
	jaFoi[0].pb(ini[1]) ;
	m[ini[0]][ini[1]] = m[ini[1]][ini[0]] ;

	while(true)
	{
		pii p0 = dist[0][ idx[0] ] , p1 = dist[1][ idx[1] ] ;

		if(p0.ff == inf && p1.ff == inf) { break ; }

		int cur = p0.ss , cameFrom = 0 ;
		if(p0.ff > p1.ff)
			cur = p1.ss, cameFrom = 1 ;

		idx[cameFrom] ++ ;

		if( marc[cur] ) { continue ; }

		int fatMult = cameFrom == 0 ? 1 : -1 ;
		int contFatMult = fatMult == -1 ? 1 : -1 ;

		for(int i : jaFoi[cameFrom])
			if( m[ini[cameFrom]][i] + m[i][cur] == m[ini[cameFrom]][cur] )
			{
				location[cur] = location[i] + m[i][cur] * contFatMult ;
				stype[cur] = stype[i] ;
				marc[cur] = true ;
				break ;
			}

		if(marc[cur]) continue ;

		location[cur] = location[ini[cameFrom]] + m[ini[cameFrom]][cur] * fatMult ;
		stype[cur] = stype[ini[!cameFrom]] ;

		jaFoi[cameFrom].pb(cur) ;
		findDistance(cur,0,0) ;


	}


}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44