Submission #139136

#	Time	Username	Problem	Language	Result	Execution time	Memory
139136		evpipis	Rail (IOI14_rail)	C++11	30 / 100	116 ms	1400 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 5005;
map<ii, int> mym;
int st1, st2;
vector<int> vec;

int dis(int a, int b){
    if (a == b) return 0;
    if (mym.count(mp(a, b))) return mym[mp(a, b)];

    if (a > b) swap(a, b);
    return mym[mp(a, b)] = getDistance(a, b);
}

bool comp1(int a, int b){
    return (dis(st1, a) < dis(st1, b));
}

bool comp2(int a, int b){
    return (dis(st2, a) < dis(st2, b));
}

void findLocation(int n, int first, int loc[], int stype[]){
    loc[0] = first;
    stype[0] = 1;

    if (n == 1)
        return;

    st1 = 0, st2 = -1;
    for (int i = 1; i < n; i++)
        if (st2 == -1 || dis(st1, i) < dis(st1, st2))
            st2 = i;

    vec.pb(st2);
    for (int i = 0; i < n; i++)
        if (i != st1 && dis(st1, i) < dis(st2, i))
            vec.pb(i);
    sort(vec.begin(), vec.end(), comp1);

    int last = -1;
    for (int i = 0; i < vec.size(); i++){
        int nex = vec[i];
        if (last == -1 || dis(st1, nex) < dis(last, nex)){
            loc[nex] = loc[st1]+dis(st1, nex);
            stype[nex] = 2;
            last = nex;
        }
        else{
            loc[nex] = loc[last]-dis(last, nex);
            stype[nex] = 1;
        }
    }

    vec.clear();
    vec.pb(st1);
    for (int i = 0; i < n; i++)
        if (i != st2 && dis(st2, i) < dis(st1, i))
            vec.pb(i);
    sort(vec.begin(), vec.end(), comp2);

    last = -1;
    for (int i = 0; i < vec.size(); i++){
        int nex = vec[i];
        if (last == -1 || dis(st2, nex) < dis(last, nex)){
            loc[nex] = loc[st2]-dis(st2, nex);
            stype[nex] = 1;
            last = nex;
        }
        else{
            loc[nex] = loc[last]+dis(last, nex);
            stype[nex] = 2;
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~
rail.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~

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