AtCoder Regular Contest 056: B - 駐車場

,

http://arc056.contest.atcoder.jp/tasks/arc056_b

以前この回に参加したときは解けず。解法が記憶に残っていたのか、今やったらすぐだった。

solution

使える頂点を逆順に追加していく。$O(N + M)$。

$i$番目の人が駐車しようとするとき、$j \lt i$番目の駐車スペースは通行できない。それ以外は通行可能。 $i$番目の人の駐車の際にも$j \lt i$番目の駐車スペースに到達可能なら$j$番目の人が駐車していなければおかしいので矛盾、到達不可能なら通行可能性を考える必要はない。

到達可能な駐車スペースが減少していくのは面倒なので、逆から見ていく。 $S$から減らしていって$i$番目の人を考えるときは、$i+1$番目の人が到達可能だった駐車スペースに加えて$i$番目の駐車スペースも到達可能とすればよい。 $i$番目の駐車スペースに$i+1$番目の人が到達可能だった駐車スペースが隣接しているならば、$i$番目の駐車スペースから今まで到達可能でなかった$j \ge i$番目な駐車スペースのみを通って到達可能なスペースが追加で到達可能。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;

int main() {
    // input
    int n, m, s; scanf("%d%d%d", &n, &m, &s); -- s;
    vector<vector<int> > g(n);
    repeat (i,m) {
        int u, v; scanf("%d%d", &u, &v); -- u; -- v;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    // solve
    vector<bool> reachable(n);
    reachable[s] = true;
    function<void (int, int)> go = [&](int i, int limit) {
        for (int j : g[i]) if (j >= limit and not reachable[j]) {
            reachable[j] = true;
            go(j, limit);
        }
    };
    vector<int> result;
    repeat_reverse (i,s+1) {
        bool found = false;
        if (reachable[i]) {
            found = true;
        } else {
            for (int j : g[i]) {
                if (reachable[j]) {
                    found = true;
                    break;
                }
            }
        }
        if (not found) continue;
        result.push_back(i);
        reachable[i] = true;
        go(i, i);
    }
    whole(reverse, result);
    // output
    for (int i : result) {
        printf("%d\n", i+1);
    }
    return 0;
}