Submission #246380

#	Time	Username	Problem	Language	Result	Execution time	Memory
246380		oscarsierra12	Rail (IOI14_rail)	C++14	8 / 100	106 ms	34808 KiB

rail

#include "rail.h"
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <set>
#include <deque>
#include <utility>
#include <sstream>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <algorithm>
#include <limits.h>

using namespace std ;

#define ff   first
#define ss   second
#define pb   push_back

typedef pair<int,int>   ii ;

int dist[5010][5010] ;

void findLocation(int N, int first, int location[], int stype[])
{
    vector <ii> fromA, fromA2 ;
    for ( int i = 1 ; i < N ; ++i ) {
        int x = getDistance ( 0, i );
        dist[0][i] = dist[i][0] = x ;
        fromA.pb ( {x, i} ) ;
    }
    set <int> befA, aftA ;
    sort ( fromA.begin(), fromA.end() ) ;
    int j = fromA[0].ss ;
    for ( int i = 0 ; i < N ; ++i ) {
        int x = getDistance ( i, j ) ;
        dist[i][j] = dist[j][i] = x ;
        if ( i == 0 ) {}
        else if ( x < dist[0][j] ) aftA.insert ( i ) ;
        else if ( dist[0][i] < x ) aftA.insert ( i ) ;
        else befA.insert ( i ) ;
        fromA2.pb ( {x, i} ) ;
    }
    sort ( fromA2.begin(), fromA2.end() ) ;
    location[0] = first ;
    stype[0] = 1 ;
    int c = -1 ;
    for ( auto i:fromA ) {
        if ( !aftA.count ( i.ss ) ) continue ;
        if ( c == -1 ) c = i.ss, location[c] = location[0] + i.ff, stype[c] = 2 ;
        else {
            int x = getDistance ( i.ss, c ) ;
            if ( dist[0][i.ss] < x ) c = i.ss, location[c] = location[0] + i.ff, stype[c] = 2 ;
            else location[i.ss] = location[c] - x, stype[i.ss] = 1 ;
        }
    }
    c = -1 ;
    for ( auto i:fromA2 ) {
        if ( !befA.count ( i.ss ) ) continue ;
        if ( c == -1 ) c = i.ss, location[c] = location[j] - i.ff, stype[c] = 1 ;
        else {
            int x = getDistance ( i.ss, c ) ;
            if ( dist[j][i.ss] < x ) c = i.ss, location[c] = location[0] - i.ff, stype[c] = 1 ;
            else location[i.ss] = location[c] + x, stype[i.ss] = 2 ;
        }
    }
    return ;
}

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