Submission #703541

#	Time	Username	Problem	Language	Result	Execution time	Memory
703541		jophyyjh	Rail (IOI14_rail)	C++14	56 / 100	515 ms	151008 KiB

rail

/**
 * [S1-3] Let d(u,v) be the dist from station u to station v.
 *  Obs1: d(.,.) is a norm.
 *      We know dist(u,v) = dist(v,u) and dist(a,b) + dist(b,c) >= dist(a,c). This
 *      means we can pre-compute the dist between every pair of nodes.
 *  Obs2: For every u, d(u,v) (v != u) achieves the min => v and u are different
 *          types of station. v is the first station we can get to after leaving u.
 *      For simplicity, we define v to be u's "conjugate" iff d(u,v) achieves
 *      the minimum over all v. It is easy to see that every node has a unique
 *      conjugate.
 *      These observations lead us to a recursive solution. Find a conjugate pair
 *      (u,v) with no other stations between them. (A pair always exists~) d(u,v) is
 *      their difference in block number. The pair splits the railway line into two
 *      parts - a left and a right part. We can determine which part a station w
 *      belongs to by finding which one of d(w,u), d(w,v) is smaller. Assign u, v to
 *      their corresponding part and recursively solve them would be good.
 * 
 * Calls needed:    n * (n - 1) / 2
 * Implementation 1                 (Solves [S1-3] (bound tight)
*/

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

typedef std::vector<int>    vec;

const int INF = 0x3f3f3f3f;


std::vector<vec> dist;
int* location;      // location of the stations, ans variable
int* s_type;        // station type, ans variable

inline void set_conj(int s, int t) {
    s_type[t] = 3 - s_type[s];
    location[t] = (s_type[s] == 1 ? 1 : -1) * dist[s][t] + location[s];
}

void solve(vec nodes, int ref) {
    if (int(nodes.size()) == 1)
        return;
    int r1 = -1, r2 = -1, min_dist = INF;
    for (int k : nodes) {
        if (k != ref && dist[k][ref] < min_dist)
            min_dist = dist[k][ref], r1 = k;
    }
    set_conj(ref, r1);
    min_dist = INF;
    for (int k : nodes) {
        if (k != r1 && dist[k][r1] < min_dist)
            min_dist = dist[k][r1], r2 = k;
    }
    set_conj(r1, r2);
    vec part1 = {r1}, part2 = {r2};
    for (int k : nodes) {
        if (k == r1 || k == r2 || s_type[k] != 0)
            continue;
        if (dist[k][r1] <= min_dist)
            set_conj(r1, k);
        else if (dist[k][r2] <= min_dist)
            set_conj(r2, k);
        else if (dist[k][r1] < dist[k][r2])
            part1.push_back(k);
        else
            part2.push_back(k);
    }
    solve(part1, r1);
    solve(part2, r2);
}

void findLocation(int n, int first, int _location[], int _s_type[]) {
    location = _location, s_type = _s_type;
    memset(s_type, 0, sizeof(int) * n);
    dist.assign(n, vec(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++)
            dist[i][j] = dist[j][i] = getDistance(i, j);
    }
    vec all_nodes(n);
    for (int i = 0; i < n; i++)
        all_nodes[i] = i;
    location[0] = first, s_type[0] = 1;
    solve(all_nodes, 0);
}

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