Submission #246635

#	Time	Username	Problem	Language	Result	Execution time	Memory
246635		oscarsierra12	Rail (IOI14_rail)	C++14	56 / 100	728 ms	99340 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] ;
vector <ii> vec[5010] ;


void findLocation(int N, int first, int location[], int stype[])
{
    for ( int i = 0 ; i < N ; ++i ) {
        for ( int j = i+1 ; j < N; ++j ) {
            int x = getDistance ( i, j ) ;
            dist[i][j] = dist[j][i] = x ;
            if ( i == 0 || vec[i].size() == 0) vec[i].pb ({x,j}) ;
            else vec[i][0] = min ( vec[i][0], {x,j} ) ;
            if ( j == 0 || vec[j].size() == 0 ) vec[j].pb ({x,i}) ;
            else vec[j][0] = min ( vec[j][0], {x, i} ) ;
        }
    }

    for ( int i = 0 ; i < N ; ++i )
        sort ( vec[i].begin(), vec[i].end()) ;

    set <int> befA, aftA ;
    vector <ii> fromA = vec[0], fromA2 ;
    int j = fromA[0].ss, pc = fromA[0].ff ;
    for ( int i = 0 ; i < N ; ++i ) {
        if ( i == j ) continue ;
        int x = dist[i][j] ;
        fromA2.pb ( {x, i} ) ;
    }
    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 ) ;
    }
//    return ;

    location[0] = first ; stype[0] = 1 ;
    for ( int i = 0 ; i+1 < N ; ++i ) {
        if ( befA.count(vec[0][i].ss) || location[vec[0][i].ss] != 0) continue ;
        location[vec[0][i].ss] = location[0] + vec[0][i].ff ;
        stype[vec[0][i].ss] = 2 ;
        for ( int k = 0 ; k < N ; ++k ) {
            if ( location[k] != 0 || befA.count(k) ) continue ;
            if ( stype[vec[k][0].ss] == 2 )
                stype[k] = 1, location[k] = location[vec[k][0].ss] - vec[k][0].ff ;
        }
    }

    vec[j].clear() ;
    for ( int i = 0 ; i+1 < N ; ++i ) {
        vec[j].pb ( fromA2[i] ) ;
        if ( !befA.count(vec[j][i].ss) || location[vec[j][i].ss] != 0) continue ;
        location[vec[j][i].ss] = location[j] - vec[j][i].ff ;
        stype[vec[j][i].ss] = 1 ;
        for ( int k = 0 ; k  < N ; ++k ) {
            if ( location[k] != 0 ) continue ;
            if ( stype[vec[k][0].ss] == 1 )
                stype[k] = 2, location[k] = location[vec[k][0].ss] + vec[k][0].ff ;
        }
    }

   /* 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 ) ;
            cout << i.ss << ' ' << c << ' ' << dist[0][c] << ' ' << dist[0][i.ss] << ' ' << x << endl ;
            if ( x == dist[0][i.ss] + dist[0][c] ) 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] + dist[j][c] ==  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 << location[i] << ' ' << stype[i] << endl ;
    return ;
}

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