Submission #246387

#	Time	Username	Problem	Language	Result	Execution time	Memory
246387		oscarsierra12	Rail (IOI14_rail)	C++14	30 / 100	96 ms	34552 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, pc = fromA[0].ff ;
    for ( int i = 0 ; i < N ; ++i ) {
        if ( i == j ) continue ;
        int x = getDistance ( i, j ) ;
        dist[i][j] = dist[j][i] = x ;
        fromA2.pb ( {x, i} ) ;
        //cout << i << ' ' << x << ' ' << dist[0][j] << ' ' << dist[0][i] << endl ;
    }
    sort ( fromA2.begin(), fromA2.end() ) ;
    pc -= fromA2[0].ff ;
    for ( int i = 0 ; i < N ; ++i ) {
        int x = dist[i][j] ;
        if ( i == 0 || x < dist[0][j] || dist[0][i] - pc < x ) {}
        else befA.insert ( i ) ;
    }
    location[0] = first ;
    stype[0] = 1 ;
    int c = -1 ;
    for ( auto i:fromA ) {
        if ( befA.count ( i.ss ) ) continue ;
//        cout << i.ff << ' ' << i.ss << ' ' << c << endl ;
        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] - pc < 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[j] - i.ff, stype[c] = 1 ;
            else location[i.ss] = location[c] + x, stype[i.ss] = 2 ;
        }
    }
//    for ( int i = 0 ; i <N; ++i ) cout << stype[i] << ' ' << location[i] << endl;
    return ;
}

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