CF827F Dirty Arkady’s Kitchen

发布于 2022-04-04  1.18k 次阅读


Problem Link

Statement

给出一个 $n$ 个点 $m$ 条边的无向图,每条边在 $l_i$ 时刻出现,$r_i$ 时刻消失。$0$ 时刻时你在 $1$ 号点上,每一时刻你都需要经过一条边移动到距离为 $1$ 的另一个点上,不能停留在一个点上不动。每个点和每条边均可经过多次。问最早到达 $n$ 号点的时间,或判断无法到达 $n$ 号点。

$n,m \le 5 \times 10^5,~0 \le l < r \le 10^9$

Solution

我们发现若我们在 $t$ 时刻从 $x$ 走到 $y$,我们可以在这一条边上反复横跳让我们在 $t + 2,~t + 4,~\dots$ 时刻均能到达 $y$,直到该边消失。由于这些能到达 $y$ 的时刻奇偶性均相同,因此考虑将每个点拆分为两个,一个为奇点一个为偶点,每次到达奇点时的时刻为奇数,到达偶点的时刻为偶数。对于一条 $x$ 向 $y$ 的边,拆点后即为 $x$ 的奇点向 $y$ 的偶点连边和 $x$ 的偶点向 $y$ 的奇点连边。

考虑在拆完点后得到的图上跑最短路,但是将最短路状态记在点上是不妥的,因为点是不会消失的,因此无法判断长于最短路的某一个路径长度是否合法。考虑将最短路状态记在边上,对每条有向边记录其最早的到达这条边起点的时间。到达一个点的最早时间即为他的所有入边的最短路的最小值加一。

Code

View On GitHub

/**
 * @file 827F.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-04-03
 *
 * @copyright Copyright (c) 2022
 * @brief
 *      My Tutorial: https://macesuted.moe/article/cf827f
 *
 */

#include <bits/stdc++.h>
using namespace std;

namespace IO {
const int SIZE = 1 << 20;
char Ibuf[SIZE], *Il = Ibuf, *Ir = Ibuf, Obuf[SIZE], *Ol = Obuf, *Or = Ol + SIZE - 1;
int cache1[100], cache2[100];
char isspace(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\f' || c == '\r'; }
char iseoln(char c) { return c == '\n' || c == '\r'; }
void fill(void) { return Ir = (Il = Ibuf) + fread(Ibuf, 1, SIZE, stdin), void(); }
void flush(void) { return fwrite(Obuf, 1, Ol - Obuf, stdout), Ol = Obuf, void(); }
char buftop(void) { return Ir == Il && (fill(), 1), *Il; }
char getch(void) { return Il == Ir ? fill(), Il == Ir ? EOF : *Il++ : *Il++; }
void putch(char x) { return *Ol++ = x, Ol == Or && (flush(), 1), void(); }
template <typename T = int>
T read(void) {
    T x = 0, f = +1;
    char c = getch();
    while (c < '0' || c > '9') (c == '-') && (f = -f), c = getch();
    while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getch();
    return x * f;
}
template <typename T>
void write(T x) {
    if (!x) return putch('0');
    if (x < 0) putch('-'), x = -x;
    int top = 0;
    while (x) cache1[top++] = x % 10, x /= 10;
    while (top) putch(cache1[--top] ^ 48);
    return;
}
template <typename T>
void writeDouble(T x, int dep = 10) {
    if (x < 0) putch('-'), x = -x;
    int64_t fx = x;
    x -= fx;
    for (int i = 0; i < dep; i++) cache2[i] = (x *= 10), x -= int(x);
    if (int(x * 10) > 4) {
        cache2[dep - 1]++;
        for (int i = dep - 1; i; i--)
            if (cache2[i] == 10) cache2[i] = 0, cache2[i - 1]++;
        if (cache2[0] == 10) cache2[0] = 0, fx++;
    }
    write(fx), putch('.');
    for (int i = 0; i < dep; i++) putch(cache2[i] ^ 48);
    return;
}
string getstr(const string& suf = "") {
    string s = suf;
    while (isspace(buftop())) getch();
    for (char* p = Il; Il != Ir; fill(), p = Il) {
        while (Il < Ir && !isspace(*Il) && *Il != EOF) Il++;
        s.append(p, Il);
        if (Il < Ir) break;
    }
    return s;
}
string getline(const string& suf = "") {
    string s = suf;
    while (iseoln(buftop())) getch();
    for (char* p = Il; Il != Ir; fill(), p = Il) {
        while (Il < Ir && !iseoln(*Il) && *Il != EOF) Il++;
        s.append(p, Il);
        if (Il < Ir) break;
    }
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (int i = begin; i < end; i++) putch(str[i]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace IO
using IO::getch;
using IO::getline;
using IO::getstr;
using IO::putch;
using IO::putstr;
using IO::read;
using IO::write;
using IO::writeDouble;

bool mem1;

#define maxn 500005

typedef tuple<int, int, int> tiii;

vector<vector<tiii>> graph;
vector<vector<tiii>::iterator> cur;
int dist[maxn];

void addEdge(int x, int y, int l, int r) {
    return l <= r &&
               (graph[x].emplace_back(l + (l & 1), r - (r & 1), y), graph[y].emplace_back(l + !(l & 1), r - !(r & 1), x), 1),
           void();
}

void solve(void) {
    int n = read(), m = read();
    graph.resize(2 * n + 1), cur.resize(2 * n + 1);
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read(), l = read(), r = read() - 1;
        addEdge(x, y + n, l, r), addEdge(y, x + n, l, r);
    }
    for (int i = 1; i <= 2 * n; i++) sort(cur[i] = graph[i].begin(), graph[i].end());
    memset(dist, 0x3f, sizeof(dist)), dist[1] = 0;
    static priority_queue<tiii, vector<tiii>, greater<tiii>> que;
    while (!que.empty()) que.pop();
    while (cur[1] != graph[1].end() && get<0>(*cur[1]) == 0) que.emplace(1, get<1>(*cur[1]) + 1, get<2>(*cur[1])), cur[1]++;
    while (!que.empty()) {
        auto [l, r, x] = que.top();
        que.pop(), dist[(x - 1) % n + 1] = min(dist[(x - 1) % n + 1], l);
        for (auto& i = cur[x]; i != graph[x].end() && get<0>(*i) <= r; i++)
            if (get<1>(*i) >= l) que.emplace(max(l, get<0>(*i)) + 1, get<1>(*i) + 1, get<2>(*i));
    }
    return write(dist[n] == 0x3f3f3f3f ? -1 : dist[n]), putch('\n');
}

bool mem2;

int main() {
    ios::sync_with_stdio(false);
#ifdef MACESUTED
    cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef MACESUTED
    cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
#endif
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话