---
tags: IOI
---
# IOI2011 Day1-1 熱帯植物園 (Tropical Garden)

## 問題

https://www.ioi-jp.org/ioi/2011/tasks/day1/garden_jpn.pdf
https://oj.uz/problem/view/IOI10_traffic

$N$ 頂点 $M$ 辺のグラフがあり、ある頂点から始めて以下のルールでグラフの上を歩きます。

- 現在いる頂点に接続している辺が 1 つなら、その辺を選んで移動する
- 現在いる頂点に接続している辺のうち、最も番号が小さい辺を選んで移動する
- ただし、前回もその辺を使っているなら、代わりに 2 番目に番号が小さい辺を選んで移動する

$Q$ 個のクエリが与えられます。
各クエリでは、 「頂点 $s$ から始めて $G_i$ 回移動したときに頂点 $P$ にいる」を満たす $s$ の個数を求めてください。

$N, M ≤ 150000$
$Q ≤ 2000$
$G_i ≤ 10^9$

## 考察

使われるのは各頂点から番号の小さい辺 2 つまで
最も番号が小さい辺が使えるかの状態を持たせると(頂点 2 倍)、なもりグラフになる。
あとはダブリングをすると $O(M+NQ\log G)$ で解ける。
これだと TLE するので、初めて $P$ にやってくる時間と $P$ にやってくる周期を求めると、 $O(M+NQ)$ で解ける。

## 実装

https://oj.uz/submission/298261

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 0x3fffffff;
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
 
void answer(int x);
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    vector g(N, array{pii{INF, -1}, pii{INF, -1}});
    // 各頂点から最も美しい 2 つの辺を持つ
    for(int i = 0; i < M; i++){
        auto [a, b] = R[i];
        if(chmin(g[a][1], {i, b}) && g[a][1] < g[a][0]) swap(g[a][0], g[a][1]);
        if(chmin(g[b][1], {i, a}) && g[b][1] < g[b][0]) swap(g[b][0], g[b][1]);
    }
    for(auto& [e1, e2] : g) if(e2.first == INF) e2 = e1;
    vector<int> next(N * 2);
    vector rev(N * 2, vector<int>());
    // 最も美しい辺が使えるかどうかで頂点を 2 倍する
    for(int i = 0; i < N; i++){
        {
            const auto [a, b] = g[i][0];
            if(a != INF){
                next[i * 2] = b * 2 + (a == g[b][0].first);
                rev[next[i * 2]].push_back(i * 2);
            }
        }
        {
            const auto [a, b] = g[i][1];
            if(a != INF){
                next[i * 2 + 1] = b * 2 + (a == g[b][0].first);
                rev[next[i * 2 + 1]].push_back(i * 2 + 1);
            }
        }
    }
    const int t1 = [&]{ // P * 2 に訪れる周期
        int at = P * 2;
        for(int i = 1; i <= N * 2; i++){
            at = next[at];
            if(at == P * 2) return i;
        }
        return INF;
    }();
    const int t2 = [&]{ // P * 2 + 1 に訪れる周期
        int at = P * 2 + 1;
        for(int i = 1; i <= N * 2; i++){
            at = next[at];
            if(at == P * 2 + 1) return i;
        }
        return INF;
    }();
    vector f1(N * 2, INF), f2(N * 2, INF); // 初めて P * 2 / P * 2 + 1 に訪れるまでの時間
    queue<int> q;
    f1[P * 2] = 0;
    q.push(P * 2);
    while(q.size()){
        int at = q.front();
        q.pop();
        for(int i : rev[at]) if(chmin(f1[i], f1[at] + 1)) q.push(i);
    }
    f2[P * 2 + 1] = 0;
    q.push(P * 2 + 1);
    while(q.size()){
        int at = q.front();
        q.pop();
        for(int i : rev[at]) if(chmin(f2[i], f2[at] + 1)) q.push(i);
    }
    for(int i = 0; i < Q; i++){
        const int K = G[i];
        int ans = 0;
        for(int i = 0; i < N; i++) ans += K >= f1[i * 2] && (K - f1[i * 2]) % t1 == 0 || K >= f2[i * 2] && (K - f2[i * 2]) % t2 == 0;
        answer(ans);
    }
}