Submission #436769

#	Time	Username	Problem	Language	Result	Execution time	Memory
436769		Odavey	Rail (IOI14_rail)	C++17	56 / 100	510 ms	98496 KiB

rail

//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#include                "rail.h"
#define MX_N            5001
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

//int getDistance(int i, int j){
//    int res;
//    cin >> res;
//    return res;
//}

int d[MX_N][MX_N];

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){
            d[i][j] = getDistance(i, j);
            d[j][i] = d[i][j];
        }
    }
    for(int i=0;i<n;++i){
        location[i] = -1;
    }
    location[0] = first;
    stype[0] = 1;
    int shortest = 1000000009;
    int B = -1;
    for(int i=1;i<n;++i){
        if(d[0][i] < shortest){
            B = i;
            shortest = d[0][i];
        }
    }
    location[B] = first+d[B][0];
    stype[B] = 2;

    shortest = 1000000009;
    int A = -1;
    for(int i=0;i<n;++i){
        if(i == B){
            continue;
        }
        if(d[B][i] < shortest){
            A = i;
            shortest = d[B][i];
        }
    }
    location[A] = location[B]-d[B][A];
    stype[A] = 1;
    vector<pair<int, int> > L, R;
    for(int i=0;i<n;++i){
        if(i == A || i == B){
            continue;
        }
        if(d[A][i] < d[B][i]){
            R.pb({d[A][i], i});
        }else{
            L.pb({d[B][i], i});
        }
    }
    sort(All(L));
    sort(All(R));
    for(auto& [dist, i] : R){
        if(location[i] != -1){
            continue;
        }
        stype[i] = 2;
        location[i] = location[A] + d[A][i];
        for(int j=0;j<n;++j){
            if(j == i){
                continue;
            }
            if(location[j] != -1){
                continue;
            }
            if(d[A][j] == d[A][i] + d[i][j]){
                location[j] = location[i] - d[i][j];
                stype[j] = 1;
            }
        }
    }
    for(auto& [dist, i] : L){
        if(location[i] != -1){
            continue;
        }
        stype[i] = 1;
        location[i] = location[B] - d[B][i];
        for(int j=0;j<n;++j){
            if(j == i){
                continue;
            }
            if(location[j] != -1){
                continue;
            }
            if(d[B][j] == d[B][i] + d[i][j]){
                location[j] = location[i] + d[i][j];
                stype[j] = 2;
            }
        }
    }
}

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