제출 #152394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152394		CaroLinda	철로 (IOI14_rail)	C++14	100 / 100	207 ms	51064 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 m[MAXN][MAXN] , loc[MAXN] , type[MAXN] ;

void run(int sc , vector<int> conj , int mult )
{

	if(conj.sz ==0) return ;

	vector<pii> aux ;

	for(int i : conj) aux.pb( {m[sc][i] , i} ) ;

	sort(aux.begin() , aux.end()) ;

	int frontier = aux[0].ss ;
	loc[frontier] = loc[sc] + m[sc][frontier] * mult ;
	type[frontier] = type[sc] == 1 ? 2 : 1 ;

	lp(i,1,aux.sz)
	{
		bool ok = true ;
		int now = aux[i].ss ;

		m[frontier][now] = getDistance(frontier, now) ;

		lp(j,0,i)
		{
			int t = aux[j].ss ;
			if( type[t] == type[sc] ) continue ;
			if( m[sc][t] * 2 + m[frontier][now] - m[sc][frontier] == m[sc][now] )
			{
				ok = false ;
				loc[now] = loc[frontier] - m[frontier][now] * mult;
				type[now] = type[sc] ;
			}
		}

		if(!ok) continue ;

		loc[now] = loc[sc] + m[sc][now] * mult ;
		type[now] = type[sc] == 1 ? 2 : 1 ;
		frontier = now ;

	}

}

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

	loc[0] = first ;
	type[0] = 1 ;

	if( n == 1 ) return ;

	vector<pii> aux ;

	lp(i,1,n) 
	{
		m[0][i] = m[i][0] = getDistance(0,i) ;
		aux.pb({m[0][i] , i}) ;
	}

	sort(aux.begin() , aux.end() ) ;

	int other = aux[0].ss ;

	loc[other] = loc[0] + m[0][other] ;
	type[other] = 2 ;

	lp(i,1,n)
		if(i != other)
			m[i][other] = m[other][i] = getDistance(i,other) ;

	vector<int> v[3] ;

	lp(i,1,n)
	{
		if( i == other ) continue ;
		int d1 = m[0][i] , d2 = m[other][i] , d = m[0][other] ;

		if( d1 == d2 + d && d2 > d ) v[0].pb(i) ;
		else if( d1 == d2 + d && d2 <= d) v[1].pb(i) ;
		else v[2].pb(i) ;
	}

	for(int i : v[1])
	{
		loc[i] = loc[other] - m[other][i] ;
		type[i] = 1 ;
	}

	run( 0 , v[2] , 1 ) ;
	run(other, v[0] , -1 ) ;

	lp(i,0,n) location[i] = loc[i] ;
	lp(i,0,n) stype[i] = type[i] ;

}

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp: In function 'void run(int, std::vector<int>, int)':
rail.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i = a ;i<b;i++)
                                   ^
rail.cpp:35:2: note: in expansion of macro 'lp'
  lp(i,1,aux.sz)
  ^~

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