TSOC '15 Contest 1 #5 - Giant Ants

    1#include <bits/stdc++.h>
    2using namespace std;
    3int main(){
    4    ios::sync_with_stdio(0); cin.tie(0);
    5    int n, m; cin >> n >> m;
    6    vector<vector<int>> adj(n + 1);
    7    for(int i = 0; i < m; i++){
    8        int a, b; cin >> a >> b;
    9        adj[a].push_back(b);
    10        adj[b].push_back(a);
    11    }
    12    int w; cin >> w;
    13    vector<unordered_set<int>> check(1); 
    14    unordered_set<int> frontier;
    15    for(int i = 0; i < w; i++){
    16        int c; cin >> c;
    17        check[0].insert(c);
    18        frontier.insert(c);
    19    }
    20    if (check[0].count(1)) {
    21        cout << "sacrifice bobhob314\n";
    22        return 0;
    23    }
    24    int time = 0;
    25    while(!frontier.empty()){
    26        unordered_set<int> next_frontier;
    27        for(int u : frontier){
    28            for(int v : adj[u]){
    29                if(!check.back().count(v)) next_frontier.insert(v);
    30            }
    31        } 
    32        if (next_frontier.empty()) break;
    33        time += 4; 
    34        if (check.size() <= time) check.resize(time + 1);
    35        check[time] = check[time - 4];
    36        for (int v : next_frontier) check[time].insert(v);
    37        frontier.swap(next_frontier);
    38    }
    39    queue<tuple<int,int,int>> nq; // node, time, dist
    40    nq.push({1, 0, 0});
    41    vector<unordered_set<int>> seen(n + 1);
    42    while(!nq.empty()){
    43        auto [cur, t, d] = nq.front(); nq.pop();
    44        for(int nxt : adj[cur]){
    45            int t2 = t + 1; 
    46            int timeKey = (t2 / 4) * 4;
    47            if (timeKey > time) timeKey = time;
    48            if (timeKey >= 0 && timeKey < check.size() && check[timeKey].count(nxt)) continue;
    49            if (seen[nxt].count(timeKey)) continue;
    50            seen[nxt].insert(timeKey);
    51            if (nxt == n){
    52                cout << d + 1 << '\n';
    53                return 0;
    54            }
    55            nq.push({nxt, t2, d + 1});
    56        }
    57    }
    58    cout << "sacrifice bobhob314" << '\n';
    59    return 0;
    60}
    61