Submission #30930

#	Time	Username	Problem	Language	Result	Execution time	Memory
30930		kajebiii	Rail (IOI14_rail)	C++14	100 / 100	146 ms	4688 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; 
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MAX_N = 5e3 + 100, MAX_M = 1e6 + 100;

int N, Fi, Se, Dix, Lo[MAX_N], Type[MAX_M];
int D[2][MAX_N];
void record(int ix, int lo, int ty) {
    Lo[ix] = lo;
    Type[lo] = ty;
}
void recordAuto(int fr, int to, int d) {
    if(Type[Lo[fr]] == 1) record(to, Lo[fr] + d, 2);
    else record(to, Lo[fr] - d, 1);
}
void findLocation(int n, int fi, int location[], int stype[]) {
    N = n; Fi = fi;
    record(0, fi, 1);

    int fminV = INF;
    for(int i=0; i<N; i++) {
        if(i == 0) continue;
        D[0][i] = getDistance(0, i);
        if(fminV > D[0][i]) {
            fminV = D[0][i];
            Dix = i;
        }
    }
    Se = Fi + fminV;
    recordAuto(0, Dix, fminV);

    vector<int> ls, rs;
    for(int i=0; i<N; i++) {
        if(i == 0 || i == Dix) continue;
        D[1][i] = getDistance(Dix, i);

        if(D[0][i] == D[1][i] + D[0][Dix]) {
            if(D[1][i] < D[0][Dix]) {
                record(i, Lo[Dix] - D[1][i], 1);
            }else{
                ls.push_back(i);
            }
        }else rs.push_back(i);
    }
    sort(ALL(ls), [&](int a, int b) {return D[1][a] < D[1][b];});
    sort(ALL(rs), [&](int a, int b) {return D[1][a] < D[1][b];});

    int nowC = 0, loC = Fi;
    for(int ix : ls) {
        int x = Se - D[1][ix];
        int d = getDistance(nowC, ix);
        int rest = loC - x;
        if(Type[loC + (d - rest) / 2] == 1) {
            recordAuto(nowC, ix, d);
        }else{
            recordAuto(Dix, ix, D[1][ix]);
            nowC = ix;
            loC = Lo[ix];
        }
    }

    int nowD = Dix, loD = Se;
    for(int ix : rs) {
        int x = Fi + D[0][ix];
        int d = getDistance(nowD, ix);
        int rest = x - loD;
        if(Type[loD - (d - rest) / 2] == 2) {
            recordAuto(nowD, ix, d);
        }else{
            recordAuto(0, ix, D[0][ix]);
            nowD = ix;
            loD = Lo[ix];
        }
    }

    for(int i=0; i<N; i++) {
        location[i] = Lo[i];
        stype[i] = Type[Lo[i]];
    }

    return;
}

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