oj.uz

답안 #152394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152394 2019-09-07T21:16:50 Z CaroLinda 철로 (IOI14_rail) C++14
100 / 100
 207 ms 51064 KB 
#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] ;

}

Compilation message

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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 764 KB Output is correct
7 Correct 2 ms 788 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 760 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 764 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 3 ms 788 KB Output is correct
10 Correct 2 ms 760 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 45588 KB Output is correct
2 Correct 163 ms 39544 KB Output is correct
3 Correct 167 ms 50936 KB Output is correct
4 Correct 165 ms 50936 KB Output is correct
5 Correct 187 ms 50964 KB Output is correct
6 Correct 207 ms 51032 KB Output is correct
7 Correct 183 ms 51064 KB Output is correct
8 Correct 161 ms 43128 KB Output is correct
9 Correct 163 ms 43896 KB Output is correct
10 Correct 161 ms 39144 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 45452 KB Output is correct
2 Correct 164 ms 39368 KB Output is correct
3 Correct 171 ms 51044 KB Output is correct
4 Correct 166 ms 50840 KB Output is correct
5 Correct 187 ms 51064 KB Output is correct
6 Correct 207 ms 50948 KB Output is correct
7 Correct 186 ms 50936 KB Output is correct
8 Correct 162 ms 43128 KB Output is correct
9 Correct 163 ms 44012 KB Output is correct
10 Correct 162 ms 39160 KB Output is correct
11 Correct 180 ms 45944 KB Output is correct
12 Correct 191 ms 47844 KB Output is correct
13 Correct 169 ms 50804 KB Output is correct
14 Correct 186 ms 50808 KB Output is correct
15 Correct 167 ms 50940 KB Output is correct
16 Correct 169 ms 50808 KB Output is correct
17 Correct 193 ms 50928 KB Output is correct
18 Correct 182 ms 50908 KB Output is correct
19 Correct 171 ms 50936 KB Output is correct
20 Correct 178 ms 39160 KB Output is correct