Hướng dẫn cho Xe buýt (Contest Practice VNOI 2021 Round 7)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Flower_On_Stone

Đặt d(i,j) là thời gian ít nhất để tới được điểm thứ \(j\) trên tuyến xe buýt thứ \(i\). Điểm thứ 0 là điểm ở góc trái trên của tuyến xe buýt này.

Đặc biệt, ta quy ước d(0,j) là trạng thái không ở trên xe buýt nào. Tạm gọi là “tuyến xe thứ 0”, tại tuyến này sẽ có đầy đủ \(W \times H\) giao điểm của lưới.

Giả sử đang ở trạng thái d(i,j) :

1/ Từ tuyến xe thứ \(i (i>0)\), ta có thể

  • Đi theo tuyến tới điểm tiếp theo \((j+1\) chia dư cho \(L)\) với \(L\) là độ dài tuyến xe
  • Xuống xe (chuyển qua “tuyến 0”)

2/ Từ “tuyến 0”, chỉ có thể

  • Lên tuyến xe thứ \(i (i>0)\) bất kì đi qua tọa độ hiện tại

Như vậy ta đã dựng xong đồ thị với số lượng đỉnh và số lượng cạnh là \(O(\)tổng chu vi \(+ W \times H)\).

Dùng thuật toán tìm đường đi ngắn nhất để giải.
Nếu dùng Dijkstra thì độ phức tạp là \(O(|V|+|E|).log(|V|)\) phép tính, sẽ TLE trong test lớn nhất.
Nếu dùng thuật toán [Dial][1], ta có thể giải trong \(O(|E|)\).

Source cọde:

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

const int MOD = 2004010501;
template <typename T>
bool minimized(T &var, const T &val)
{
    if (val < var)
        return var = val, true;
    return false;
}

const int N = 1005;
int length[N], start[N];

struct Coord
{
    int x, y;
    Coord(int x = 0, int y = 0) : x(x), y(y) {}
    bool operator==(const Coord &rhs) const
    {
        return x == rhs.x and y == rhs.y;
    }
};

struct Pos
{
    int bus_id, idx;
    Pos(int bus_id = 0, int idx = 0) : bus_id(bus_id), idx(idx) {}
};
vector<Pos> passing_routes[N][N];

int get_idx[N][N];
vector<int> dist[N];
#define Dist(p) dist[p.bus_id][p.idx]
vector<Coord> pos[N];

// tìm thời điểm đầu tiên sau t mà xe buýt i tới được vị trí j
// xe buýt i tới j đầu tiên tại lúc start[i]+j
int soonest(int i, int j, const int &t)
{
    int first = (start[i] + j) % length[i];
    first += (max(0, t - first) + length[i] - 1) / length[i] * length[i];
    return first;
}

deque<Pos> buckets[4 * N];
int dial(Coord sta, Coord fin)
{
    if (sta == fin)
        return 0;
    for (int i = 0; i < N; i++)
        if (!dist[i].empty())
            fill(begin(dist[i]), end(dist[i]), MOD);

    Pos _sta(0, get_idx[sta.x][sta.y]);
    Dist(_sta) = 0;
    buckets[0].push_back(_sta);

    int modulo = 4 * N;
    int max_dist = 2 * N * modulo; // 2*sigma(perimeter)
    for (int dis = 0, rem = 0; dis <= max_dist; dis++)
    {
        int siz = buckets[rem].size();
        while (siz-- > 0)
        {
            Pos cur = buckets[rem].front();
            buckets[rem].pop_front();
            if (Dist(cur) < dis)
                continue;
            Coord cd = pos[cur.bus_id][cur.idx];
            if (cd == fin)
                return dis;
            if (cur.bus_id > 0)
            {
                // follow route
                Pos nxt = cur;
                if (++nxt.idx == length[cur.bus_id])
                    nxt.idx = 0;
                if (minimized(Dist(nxt), dis + 1))
                    buckets[(rem + 1) % modulo].push_back(nxt);
                // get off the bus
                nxt = Pos(0, get_idx[cd.x][cd.y]);
                if (minimized(Dist(nxt), dis + 1))
                    buckets[(rem + 1) % modulo].push_back(nxt);
            }
            else
            {
                // get on any bus
                for (auto ps : passing_routes[cd.x][cd.y])
                {
                    int ti = soonest(ps.bus_id, ps.idx, dis);
                    if (minimized(Dist(ps), ti))
                    {
                        ti %= modulo;
                        if (ti == rem)
                            ++siz, buckets[rem].push_front(ps);
                        else
                            buckets[ti].push_back(ps);
                    }
                }
            }
        }
        rem++;
        if (rem == modulo)
            rem = 0;
    }
    return MOD;
}

int main()
{
#define task "bus"
    if (fopen(task ".inp", "r"))
    {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    int width, height;
    Coord sta, fin;
    scanf("%d%d%d%d%d%d", &width, &height, &sta.x, &sta.y, &fin.x, &fin.y);
    for (int x = 1; x <= width; x++)
        for (int y = 1; y <= height; y++)
            get_idx[x][y] = pos[0].size(),
            pos[0].push_back(Coord(x, y));
    dist[0].resize(width * height);

    int num_buses;
    scanf("%d", &num_buses);
    for (int i = 1; i <= num_buses; i++)
    {
        int x, y, u, v, t;
        scanf("%d%d%d%d%d", &x, &y, &u, &v, &t);
        length[i] = 2 * (u - x + v - y);
        start[i] = (-t + length[i]) % length[i];
        for (int xx = x; xx <= u; xx++)
            pos[i].push_back(Coord(xx, y));
        for (int yy = y + 1; yy <= v; yy++)
            pos[i].push_back(Coord(u, yy));
        for (int xx = u - 1; xx >= x; xx--)
            pos[i].push_back(Coord(xx, v));
        for (int yy = v - 1; yy > y; yy--)
            pos[i].push_back(Coord(x, yy));
        assert((int)pos[i].size() == length[i]);
        dist[i].resize(length[i]);
#define ps pos[i][j]
        for (int j = 0; j < length[i]; j++)
            passing_routes[ps.x][ps.y].push_back(Pos(i, j));
#undef ps
    }
    int res = dial(sta, fin);
    printf("%d", res);
}

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.