Submission #1007772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007772		hotboy2703	Rail (IOI14_rail)	C++14	30 / 100	41 ms	652 KiB

rail

#include "rail.h"

#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
namespace{
    const ll MAXN = 5e3+5;
    ll n;
    ll dist0[MAXN];
    ll dista[MAXN];
    ll a;
}
void findLocation(int N, int first, int location[], int stype[])
{
    location[0] = first,stype[0] = 1;
    if (n==1){
        return;
    }
    n = N;
    for (ll i = 1;i < n;i ++){
        dist0[i] = getDistance(0,i);
    }

    a = 1;
    for (ll i = 1;i < n;i ++){
        if (dist0[i] < dist0[a])a=i;
    }
    location[a] = location[0] + dist0[a];
    stype[a] = 2;
//    cout<<a<<' '<<location[a]<<'\n';
    for (ll  i = 1;i < n;i ++){
        if (i != a)dista[i] = getDistance(a,i);
    }
    vector <ll> all0,alla;
    for (ll i = 1;i < n;i ++){
        if (i != a){
            if (dist0[i] < dista[i])all0.push_back(i);
            else alla.push_back(i);
        }
    }
    sort(all0.begin(),all0.end(),[&](ll x,ll y){return dist0[x] < dist0[y];});
    for (ll i = 0;i < sz(all0);i ++){
        ll j = i;
        location[all0[i]] = dist0[all0[i]]+location[0];
        stype[all0[i]] = 2;
        while (j + 1 < sz(all0)){
            ll dick = getDistance(all0[i],all0[j+1]);
            if (dick + dist0[all0[i]] == dist0[all0[j+1]]){
                j++;
                location[all0[j]] = location[all0[i]] - dick;
                stype[all0[j]] = 1;
            }
            else{
                break;
            }
        }
        i = j;
    }

    sort(alla.begin(),alla.end(),[&](ll x,ll y){return dista[x] < dista[y];});
    for (ll i = 0;i < sz(alla);i ++){
        ll j = i;
        location[alla[i]] = -dista[alla[i]]+location[a];
        stype[alla[i]] = 1;
        while (j + 1 < sz(alla)){
            ll dick = getDistance(alla[i],alla[j+1]);
            if (dick + dista[alla[i]] == dista[alla[j+1]]){
                j++;
                location[alla[j]] = location[alla[i]] + dick;
                stype[alla[j]] = 2;
            }
            else{
                break;
            }
        }
        i = j;
    }
//    for (ll j = 0;j < n; j++){
//        cout<<stype[j]<<' '<<location[j]<<'\n';
//    }
}

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