제출 #399416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399416		egorlifar	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	297 ms	26148 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 = 250228;


int n, m;
vector<int> g[MAXN];
int k;
int l[MAXN];
vector<int> v[MAXN];
int who[MAXN];
vector<int> dist[MAXN];
int pos[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 < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].pb(b);
        g[b].pb(a);
    } 
    cin >> k;
    for (int i = 0; i < n; i++) {
        pos[i] = -1;
    }
    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--;
            who[u] = i;
            pos[u] = j;
            v[i].pb(u);
        }
    }
    for (int i = 0; i < n; i++) {
        dist[i].resize(max(l[who[i]] * 2, 4));
        for (auto &h: dist[i]) {
            h = 1e9;
        }
    }
    set<pair<int, pair<int, int> > > q;
    q.insert(mp(0, mp(0, 0)));
    dist[0][0] = 0;
    while (!q.empty()) {
        auto f = *q.begin();
        q.erase(f);
        int u = f.second.first;
        int t = f.second.second;
        for (int shift = 0; shift <= 2; shift++) {
            if ((dist[u][t] + shift) % max(l[who[u]], 1) == pos[u]) {
                break;
            }
            int nt = (dist[u][t] + shift) % max(l[who[u]] * 2, 4);
            if (dist[u][nt] > dist[u][t] + shift) {
                q.erase(mp(dist[u][nt], mp(u, nt)));
                dist[u][nt] = dist[u][t] + shift;
                q.insert(mp(dist[u][nt], mp(u, nt)));
            }
            for (auto h: g[u]) {
                nt = (dist[u][t] + 1 + shift) % max(l[who[h]] * 2, 4);
                if (dist[h][nt] > dist[u][t] + 1 + shift && pos[h] != (dist[u][t] + 1 + shift) % max(l[who[h]], 1)) {
                    if (who[u] == who[h] && who[u]) {
                        if (pos[u] == (dist[u][t] + 1 + shift) % l[who[u]] && pos[h] == (dist[u][t] + shift) % l[who[u]]) {
                            continue;
                        }
                    }
                    q.erase(mp(dist[h][nt], mp(h, nt)));
                    dist[h][nt] = dist[u][t] + 1 + shift;
                    q.insert(mp(dist[h][nt], mp(h, nt)));
                }
            }
        }
    }
    int ans = 1e9;
    for (auto y: dist[n - 1]) {
        chkmin(ans, y);
    }
    if (ans > 1e8) {
        cout << "impossible\n";
        return 0;
    }
    cout << ans << '\n';
    return 0;
}
 

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