Submission #399438

#	Time	Username	Problem	Language	Result	Execution time	Memory
399438		egorlifar	From Hacks to Snitches (BOI21_watchmen)	C++17	100 / 100	3349 ms	119488 KiB

watchmen

/*
KAMUI!
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓██████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓███▓▓▓▓▓▓▓▓▓▓█████▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓███▓▒▒░▒▒▒▒▒░░░▒▒▒▓▓███▓▓▓▓▓▓▓ 
▓▓▓▓▓▓█▓▒▒▒▓▓████████▓▒▒░▒▒▒▓██▓▓▓▓▓▓
▓▓▓▓██▒▓████████████████▓░▒▒▒▒▓██▓▓▓▓ 
▓▓▓██▓███████▓▒░░░░░░░▒███▒░░▒▒▒██▓▓▓ 
▓▓█████████▓░░░░░░░░░░░░░██▓▓██████▓▓ 
▓▓█▒▓███████████▓▓▒▒▒▓▓██████████▓█▓▓ 
▓██▒▒▒███████████████████████████▓▓█▓ 
▓█▓▒▒░░████████▒░░░░▓███████████▓░▒█▓ 
▓█▒▒▒░██░▒████░░░░░░█████░░████▓░░▒█▓ 
▓█▒▒▒▒██░░░██▓░░░░░░░███▒░░████▒▒▒▒█▓ 
▓█▓▒▒▒██▒░░░▓█▓░░░░░▓█▓░░░▓███▓▒▒░▓█▓ 
▓█▓▒▒▒███░░░░████████▓░░░░░████▒▒▒▓█▓ 
▓▓█▒▒░▓███░░░▒███████▒░░░▒███▓▒▒▒▒█▓▓ 
▓▓██▒▒░████▒░░███████░░░▓███▓░▒▒▒██▓▓ 
▓▓▓██▒▒▒█████▓░░██████▒▓███▓▒░▒▒██▓▓▓ 
▓▓▓▓██▓▒░▓██████████████▓▒░▒▒▒▓██▓▓▓▓ 
▓▓▓▓▓▓██▓░▒▓█████████▒░░▒▒▒▒▓██▓▓▓▓▓▓ 
▓▓▓▓▓▓▓███▓▒▒▓██████▓░▒▒▒▓▓███▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓███▓▓▓▓███▓▓▓████▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓███████████▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
*/
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";
const int MAXN = 250000, MAXK = 1000, inf = 1 << 29;


int N, M, K, L[MAXK], r[MAXN], t[MAXN], c[MAXN];
vector<int> e[MAXN], V[MAXK], dp[MAXN];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   // read(FILENAME);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        r[i] = 0, t[i] = -1;
    }
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        e[u].pb(v);
        e[v].pb(u);
    }
    cin >> K;
    L[0] = 1;
    for (int i = 1; i <= K; i++) {
        cin >> L[i];
        for (int j = 0; j < L[i]; j++) {
            int u;
            cin >> u;
            u--;
            V[i].pb(u);
            r[u] = i;
            t[u] = j;
        }
    }
    for (int i = 0; i < N; i++) {
        dp[i].resize(L[r[i]]);
        for (int j = 0; j < L[r[i]]; j++) {
            dp[i][j] = inf;
        }
    }
    priority_queue<tuple<int, int, int>> pq;
    auto update = [&](int i, int d) {
        int o = d % L[r[i]];
        if (o != t[i] && d < dp[i][o]) {
            dp[i][o] = d;
            pq.emplace(-d, i, o);
        }
    };
    update(0, 0);
    while (!pq.empty()) {
        auto [d, i, o] = pq.top();
        pq.pop();
        d *= -1;
        if (d != dp[i][o]) {
            continue;
        }
        for (int k = 0; k < sz(e[i]); k++) {
            int j = e[i][k];
            if (!r[i] || r[j] != r[i] || (t[j] + 1) % L[r[i]] != t[i] || t[j] != o) {
                update(j, d + 1);
            }
            if (!r[i] && r[j]) {
                update(j, d + 1 + (t[j] + L[r[j]] - d % L[r[j]]) % L[r[j]]);
            }
            bool re = false;
            if (r[i] && r[j] && (r[j] != r[i] || ((t[j] + 1) % L[r[i]] != t[i] && (t[i] + 1) % L[r[i]] != t[j]))) {
                int tnj = d + (t[j] + L[r[j]] - d % L[r[j]]) % L[r[j]];
                int tnji = tnj + (t[i] + L[r[i]] - tnj % L[r[i]]) % L[r[i]];
                if (tnj != tnji) {
                    update(j, tnj + 1);
                    re = true;
                } else {
                    int nd = tnj + (o + L[r[i]] - t[i]) % L[r[i]];
                    update(j, nd + 1);
                    if (L[r[j]] % L[r[i]] != 0 && (L[r[i]] % L[r[j]] != 0 || (t[i] + L[r[i]] - o) % L[r[i]] >= L[r[j]])) {
                        update(j, nd + 1 + (t[j] + L[r[j]] - nd % L[r[j]]) % L[r[j]]);
                    }
                }
            }
            if (!r[i] || !r[j] || re) {
                swap(e[i][k], e[i].back());
                e[i].pop_back();
                k--;
            }
        }
        update(i, d + 1);
    }
    if (dp[N - 1][0] == inf) {
        cout << "impossible\n";
    } else {
        cout << dp[N - 1][0] << '\n';
    }
    return 0;
}

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