제출 #399416

#제출 시각아이디문제언어결과실행 시간메모리
399416egorlifarFrom Hacks to Snitches (BOI21_watchmen)C++17
0 / 100
297 ms26148 KiB
/* 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...