Submission #673665

#	Time	Username	Problem	Language	Result	Execution time	Memory
673665		stanislavpolyn	From Hacks to Snitches (BOI21_watchmen)	C++17	15 / 100	6022 ms	114272 KiB

watchmen

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
 
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
 
using namespace std;
 
mt19937_64 rng(228);
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
 
template <typename T>
bool umn(T& a, T b) { return (a > b ? (a = b, 1) : 0); }
template <typename T>
bool umx(T& a, T b) { return (a < b ? (a = b, 1) : 0); }
 
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
 
const int N = 3e5 + 5;
 
int n, m, k;
ve<int> g[N];
ve<int> v[N];
bool mark[N];
 
ve<int> dp[N];
int bad[N];
int nxt[N];
queue<array<int, 3>> q;
 
int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif
 
    cin >> n >> m;
 
    fr (i, 1, m) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    cin >> k;
    fr (i, 1, k) {
        int sz;
        cin >> sz;
        v[i].resize(sz);
        int idx = 0;
 
        int prv = -1;
        fe (x, v[i]) {
            cin >> x;
            if (prv != -1) nxt[prv] = x;
            prv = x;
            assert(!mark[x]);
            mark[x] = 1;
            dp[x].resize(sz, 1e9);
            bad[x] = idx;
            idx++;
        }
        nxt[v[i].back()] = v[i][0];
    }
 
    fr (i, 1, n) {
        if (!mark[i]) {
            dp[i].resize(2, 1e9);
            bad[i] = -1;
            nxt[i] = -1;
        }
    }
 
    assert(!mark[1]);
    assert(!mark[n]);
//    assert(k == 1);
 
    dp[1][0] = 0;
    q.push({0, 1, 0});
 
//    fr (i, 1, n) {
//        cout << i << " " << bad[i] << "\n";
//    }
 
    while (sz(q)) {
        int v = (q.front())[1];
        int rem = (q.front())[2];
        int t = (q.front())[0];
        q.pop();
        assert(dp[v][rem] == t);
        assert(rem == t % sz(dp[v]));
 
        int nt = (t + 1) % sz(dp[v]);
 
        bool good = 0;
        fe (to, g[v]) {
            if (!mark[to] && min(dp[to][0], dp[to][1]) < t) {
                good = 1;
                break;
            }
        }
 
        if (bad[v] != nt || good) {
            if (dp[v][nt] > t + 1) {
                dp[v][nt] = t + 1;
                q.push({dp[v][nt], v, nt});
            }
        }
 
        if (rem == bad[v]) continue;
 
        fe (to, g[v]) {
            int nt = (t + 1) % sz(dp[to]);
            if (bad[to] == nt) continue;
            if ((t + 1) % sz(dp[v]) == bad[v] && nxt[to] == v) continue;
 
            if (to == n) {
                cout << t + 1 << "\n";
                return 0;
            }
 
 
            if (dp[to][nt] > t + 1) {
                dp[to][nt] = t + 1;
                q.push({dp[to][nt], to, nt});
            }
        }
    }
 
    int mn = *min_element(all(dp[n]));
 
    if (mn == int(1e9)) {
        cout << "impossible\n";
        return 0;
    }
 
 
 
    cout << mn << "\n";
 
    return 0;
}

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