Submission #49386

#	Time	Username	Problem	Language	Result	Execution time	Memory
49386		imeimi2000	Rail (IOI14_rail)	C++17	100 / 100	127 ms	892 KiB

rail

#include "rail.h"
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 5000;
int n;
int d0[MAXN];
int d1[MAXN];
int rd[MAXN];
int st[MAXN];
int *l, *t;

void calc(vector<int> &ps, int s) {
    sort(ps.begin(), ps.end(), [&](int i, int j) { return rd[i] < rd[j]; });
    int tp = 0;
    l[ps[0]] = l[s] + rd[ps[0]];
    t[ps[0]] = 2;
    int mx = ps[0];
    st[tp++] = l[mx] << 1;
    for (int i = 1; i < ps.size(); ++i) {
        int fn = (l[mx] << 1) + rd[ps[i]] - rd[mx] - getDistance(ps[i], mx);
        if (find(st, st + tp, fn) - st != tp) {
            l[ps[i]] = fn - rd[ps[i]] - l[s];
            t[ps[i]] = 1;
        }
        else {
            l[ps[i]] = l[s] + rd[ps[i]];
            t[ps[i]] = 2;
            st[tp++] = l[ps[i]] << 1;
            mx = ps[i];
        }
    }
}

void findLocation(int N, int f, int _l[], int _t[]) {
    n = N;
    l = _l;
    t = _t;
    
    int mn = 1;
    for (int i = 1; i < n; ++i) {
        d0[i] = getDistance(0, i);
        if (d0[i] < d0[mn]) mn = i;
    }
    d1[0] = d0[mn];
    vector<int> vt1, vt2;
    rd[0] = rd[mn] = d1[0];
    vt1.push_back(0);
    vt2.push_back(mn);
    for (int i = 1; i < n; ++i) {
        if (mn == i) continue;
        d1[i] = getDistance(mn, i);
        if (d0[i] == d1[i] + d1[0]) vt1.push_back(i), rd[i] = d1[i];
        else vt2.push_back(i), rd[i] = d0[i];
    }
    l[0] = f;
    t[0] = 1;
    calc(vt2, 0);
    l[mn] = -(f + d1[0]);
    t[mn] = 1;
    calc(vt1, mn);
    l[mn] = -l[mn];
    t[mn] = 2;
    for (int i : vt1) {
        l[i] = -l[i];
        t[i] ^= 3;
    }
}

Compilation message (stderr)

rail.cpp: In function 'void calc(std::vector<int>&, int)':
rail.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < ps.size(); ++i) {
                     ~~^~~~~~~~~~~

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