Submission #1063530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063530		ArthuroWich	Rail (IOI14_rail)	C++17	30 / 100	43 ms	608 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
int dist[5005][5005];
int query(int i, int j) {
    if (dist[i][j]) {
        return dist[i][j];
    }
    dist[i][j] = getDistance(i, j);
    return dist[i][j];
}
void findLocation(int n, int f, int loc[], int st[]) {
    int l = 0, r;
    loc[0] = f;
    st[0] = 1;
    if (n == 1) {
        return;
    }
    vector<pair<int, int>> ord;
    for (int i = 1; i < n; i++) {
        ord.push_back({query(0, i), i});
    }
    sort(ord.rbegin(), ord.rend());
    r = ord.back().second;
    loc[r] = loc[0]+ord.back().first;
    st[r] = 2;
    ord.pop_back();
    while(!ord.empty()) {
        auto [_, i] = ord.back();
        ord.pop_back();
        int ld = query(l, i), rd = query(r, i);
        if (rd > ld) {
            loc[i] = loc[l]+ld;
            st[i] = 2;
        } else {
            loc[i] = loc[r]-rd;
            st[i] = 1;
        }
    }
}

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