Submission #1156836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156836		maslinnik	From Hacks to Snitches (BOI21_watchmen)	C++20	25 / 100	6084 ms	103784 KiB

watchmen

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#define sz(a) (int)a.size()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

typedef long long ll;

using namespace std;

const int INF = 1e9;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> gr(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    int k;
    cin >> k;
    vector<vector<int>> v(k);
    vector<int> head(k);
    vector<int> idx(n, -1), pos(n, -1);
    int vertex_cnt = n;
    for (int i = 0; i < k; ++i) {
        int len;
        cin >> len;
        head[i] = vertex_cnt;
        vertex_cnt += len * len;
        v[i].resize(len);
        for (int j = 0; j < len; ++j) {
            cin >> v[i][j];
            v[i][j]--;
            idx[v[i][j]] = i;
            pos[v[i][j]] = j;
            for (int it = 0; it < len; ++it) {
                idx.push_back(i);
                pos.push_back(j);
            }
        }
    }
    auto get_v = [&](int i, int d) {
        if (idx[i] == -1) return i;
        int j = idx[i];
        return head[j] + sz(v[j]) * pos[i] + d % sz(v[j]);
    };
    auto get_orig = [&](int i) {
        if (idx[i] == -1) return i;
        int j = idx[i];
        return v[j][pos[i]];
    };
    auto watchman_at = [&](int d, int i) {
        return v[i][d % sz(v[i])];
    };
    auto when_watchman = [&](int d, int i) {
        int j = idx[i];
        assert(j != -1);
        int res = d - d % sz(v[j]) + pos[i];
        if (res >= d) {
            return res;
        } else {
            return res + sz(v[j]);
        }
    };
    for (int i = 0; i < n; ++i) {
        sort(all(gr[i]), [&](int a, int b) {
            return idx[a] > idx[b];
        });
    }
    vector<int> dist(vertex_cnt, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> st;
    auto update = [&](int i, int d) {
        i = get_v(i, d);
        if (dist[i] > d) {
//            cerr << "updated " << get_orig(i) << " with " << d << '\n';
            dist[i] = d;
            st.push({dist[i], i});
        }
    };
    update(0, 0);
    while (!st.empty()) {
        auto [d, i] = st.top();
        st.pop();
        if (dist[i] != d) continue;
        i = get_orig(i);
        while (!gr[i].empty() && idx[gr[i].back()] == -1) {
            int to = gr[i].back();
            gr[i].pop_back();
            update(to, d + 1);
        }
        for (int to : gr[i]) {
            if (idx[i] == -1) {
                if (idx[to] == -1) {
                    update(to, d + 1);
                } else {
                    int watchman_this_move = watchman_at(d + 1, idx[to]);
                    if (watchman_this_move == to) {
                        update(to, d + 2);
                    } else {
                        update(to, d + 1);
                    }
                    int watchman_passes = when_watchman(d + 1, to);
                    update(to, watchman_passes + 1);
                }
            } else if (idx[to] == -1) {
                update(to, d + 1);
            } else if (idx[to] == idx[i]) {
                if (watchman_at(d, idx[i]) == to && watchman_at(d + 1, idx[i]) == i || watchman_at(d + 1, idx[i]) == to) {
                    continue;
                }
                update(to, d + 1);
            } else {
                for (int cur_d : {d, d + sz(v[idx[i]])}) {
                    int can_stay_until = when_watchman(cur_d, i);
                    if (watchman_at(cur_d + 1, idx[to]) == to) {
                        if (can_stay_until > cur_d + 1) {
                            update(to, cur_d + 2);
                        }
                    } else {
                        update(to, cur_d + 1);
                    }
                    int watchman_passes = when_watchman(cur_d + 1, to);
                    if (can_stay_until > watchman_passes) {
                        update(to, watchman_passes + 1);
                    }
                }
            }
        }
    }
    if (dist[n - 1] == INF) {
        cout << "impossible\n";
    } else {
        cout << dist[n - 1] << '\n';
    }
}

int main() {
#ifdef LOCAL
    freopen("../in.txt", "r", stdin);
    //freopen("../out.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif

    solve();

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20