Submission #786372

#	Time	Username	Problem	Language	Result	Execution time	Memory
786372		lollipop	Rail (IOI14_rail)	C++17	100 / 100	78 ms	60812 KiB

rail

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 6e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "rail.h"
//#include "grader.h"

//typedef struct Station {
//  int index;
//  int type;
//  int location;
//  int L, R;
//} STATION;
//static long long cnt;
//static int S, SUBTASK;
//static STATION stations[10004];
//int getDistance(int x, int y) {
//  cnt++;
//  if (x == y)
//    return 0;
//  if (x < 0 || x >= S || y < 0 || y >= S)
//    return -1;
//  if (stations[x].location > stations[y].location) {
//    int tmp = x;
//    x = y;
//    y = tmp;
//  }
//  int ret = 0;
//  if (stations[x].type == 1 && stations[y].type == 1) {
//    ret = stations[stations[y].R].location - stations[x].location +
//          stations[stations[y].R].location - stations[y].location;
//  } else if (stations[x].type == 1 && stations[y].type == 2) {
//    ret = stations[y].location - stations[x].location;
//  } else if (stations[x].type == 2 && stations[y].type == 2) {
//    ret = stations[x].location - stations[stations[x].L].location +
//          stations[y].location - stations[stations[x].L].location;
//  } else if (stations[x].type == 2 && stations[y].type == 1) {
//    ret = stations[x].location - stations[stations[x].L].location +
//          stations[stations[y].R].location - stations[stations[x].L].location +
//          stations[stations[y].R].location - stations[y].location;
//  }
//  return ret;
//}


map < int , int > been ;
int d[ 5005 ][ 5005 ] ; 
void findLocation(int n, int pos, int ps[], int tp[]){
	 ps[ 0 ] = pos ;
	 tp[ 0 ] = 1 ;
	 if( n == 1 ) return ; 
	 vector < pair < int , int > > v ; 
	 for( int i = 1 ; i < n ; i ++ ){
	 	int x = getDistance( 0 , i ) ;
	 	d[ 0 ][ i ] = x ; 
	 	d[ i ][ 0 ] = d[ 0 ][ i ] ; 
	 	v.pb( { x , i } ) ;
	 }
	 sort( v.begin() , v.end() ) ; 
	 vector < int > ri , li ; 
	 int x = v[ 0 ].s ; 
	 for( auto yy : v ){
	 	int y = yy.s ; 
	 	if( yy == v[ 0 ] ){
	 		d[ x ][ 0 ] = v[ 0 ].f ;  
		}
	 	if( yy == v[ 0 ] ) continue ;
	 	d[ x ][ y ] = getDistance( x , y ) ; 
	 	d[ y ][ x ] = d[ x ][ y ] ; 
	 	if( d[ x ][ y ] < d[ x ][ 0 ] ){
	 	   ri.pb( y ) ; 
		   continue ;	
		}
   //     cout << y << " " << d[ 0 ][ y ] << " " << d[ 0 ][ x ] << " " << d[ x ][ y ] << endl ; 
		if( d[ 0 ][ y ] == d[ 0 ][ x ] + d[ x ][ y ] ){
			li.pb( y ) ;
		    continue ; 
		}
		ri.pb( y ) ; 
		continue ; 
	 }
	 pair < int , int > l , r ;
	 l = { pos , 0 } ;
	 been[ pos ] = 1 ;
	 r = { pos + v[ 0 ].f , v[ 0 ].s } ;
	 been[ pos + v[ 0 ].f ] = 2 ; 
	 ps[ v[ 0 ].s ] = pos + v[ 0 ].f ; 
	 tp[ v[ 0 ].s ] = 2 ; 
	 int y = v[ 0 ].s ; 
	 int cur = v[ 0 ].f + pos ; 
//	 debug ; 
	 for( auto x : ri ){
	 //	cout << x <<endl ; 
	 	d[ y ][ x ] = getDistance( y , x ) ;  
	 	d[ x ][ y ] = d[ y ][ x ] ; 
	 	int z = d[ 0 ][ x ] - d[ 0 ][ y ] - d[ y ][ x ] ;
	 	z /= 2 ;
	 	int pos = cur + z ;
	 	if( been[ pos ] != 2 ){
	 	   cur = d[ 0 ][ x ] + ps[ 0 ] ; 
	 	   been[ cur ] = 2 ; 
		   y = x ; 
		   tp[ x ] = 2 ;
		   ps[ x ] = cur ; 
		   continue ;	 	
		}
		else{
			tp[ x ] = 1 ;
			int pps = cur - d[ y ][ x ] ;
			been[ pps ] = 1 ; 
			ps[ x ] = pps ; 
			continue ;
		}
	//	cout << ps[ x ] << " " << tp[ x ] << endl ;
	 }
	 int cr = ps[ 0 ] ; 
	int ll = 0 ; 
	 y = v[ 0 ].s ; 
	 x = y ; 
	 for( auto z : li ){
	 	d[ ll ][ z ] = getDistance( ll , z ) ;
	 	d[ z ][ ll ] = d[ ll ][ z ] ; 
		int Z = d[ x ][ z ] - d[ x ][ ll ] - d[ ll ][ z ] ; 
		Z /= 2 ;
		int pos = cr - Z ; 
	    if( been[ pos ] != 1 ){
	    	tp[ z ] = 1 ;
	    	int pss = ps[ x ] - d[ x ][ z ] ; 	
			been[ pss ] = 1 ; 
			if( pss < cr ){
				ll = z ; 
			}
	    	cr = min( cr , pss ) ;
	    	ps[ z ] = pss ; 
		}
		else{
			tp[ z ] = 2 ; 
			int pss = cr + d[ ll ][ z ] ;			
			been[ pss ] = 2 ;
			ps[ z ] = pss ; 
		}
	 }
	 return ; 
	 
}
/*
2
6
1 3
2 6
2 7
1 1
1 0
2 8
*/



//static int cmp_fun_1(const void *a, const void *b) {
//  STATION c, d;
//  c = *(STATION *)(a);
//  d = *(STATION *)(b);
//  return c.location < d.location ? -1 : 1;
//}
//
//static int cmp_fun_2(const void *a, const void *b) {
//  STATION c, d;
//  c = *(STATION *)(a);
//  d = *(STATION *)(b);
//  return c.index < d.index ? -1 : 1;
//}
//
//static void now_I_want_to_getLR() {
//  int now = stations[S - 1].index, i;
//  for (i = S - 2; i >= 0; i--) {
//    stations[i].R = now;
//    if (stations[i].type == 2)
//      now = stations[i].index;
//  }
//  now = stations[0].index;
//  for (i = 1; i < S; i++) {
//    stations[i].L = now;
//    if (stations[i].type == 1)
//      now = stations[i].index;
//  }
//}
//
//
//
//static void getInput() {
//  assert(scanf("%d", &SUBTASK) == 1);
//  assert(scanf("%d", &S) == 1);
//  int s;
//  for (s = 0; s < S; s++) {
//    int type, location;
//    assert(scanf(" %d %d", &type, &location) == 2);
//    stations[s].index = s;
//    stations[s].location = location;
//    stations[s].type = type;
//    stations[s].L = -1;
//    stations[s].R = -1;
//  }
//  qsort(stations, S, sizeof(STATION), cmp_fun_1);
//  now_I_want_to_getLR();
//  qsort(stations, S, sizeof(STATION), cmp_fun_2);
//}
//
//static int serverGetFirstStationLocation() { return stations[0].location; }
//
//static int location[10005];
//static int type[10005];
//static int ok = 1;
//
//int main() {
//  int i;
//  getInput();
//  cnt = 0;
//
//  findLocation(S, serverGetFirstStationLocation(), location, type);
//  if (SUBTASK == 3 && cnt > S * (S - 1))
//    ok = 0;
//  if (SUBTASK == 4 && cnt > 3 * (S - 1))
//    ok = 0;
//
//  for (i = 0; i < S; i++)
//    if (type[i] != stations[i].type || location[i] != stations[i].location)
//      ok = 0;
//  if (ok == 0)
//    printf("Incorrect");
//  else
//    printf("Correct");
//  return 0;
//}

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