Submission #600757

#	Time	Username	Problem	Language	Result	Execution time	Memory
600757		Arnch	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	1672 ms	54624 KiB

watchmen

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int a[N], d[N];
vector<pair<int, int> > can[N];
vector<int> adj[N];

bool ok(int u, int t) {
	for(auto i : can[u]) {
		if(i.first > t) continue;
		if((t - i.first) % i.second == 0) return false;
	}
	return true;
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);
	
	int n, m; cin >>n >>m;
	for(int i = 0; i < m; i++) {
		int u, v; cin >>u >>v;
		adj[u].push_back(v), adj[v].push_back(u);
	}
	int k; cin >>k;
	for(int i = 0; i < k; i++) {
		int l; cin >>l;
		for(int j = 0; j < l; j++) {
			cin >>a[j];
			can[a[j]].push_back({j, l});
		}
	}
	assert(k == 1);

	memset(d, 63, sizeof(d));
	d[1] = 0;
	set<pair<int, int> > st;
	st.insert({d[1], 1});

	int tim = 0;
	
	while(!st.empty()) {
		tim++;
		int p = st.begin() -> second; st.erase(st.begin());
		if(p == n) {
			cout<<d[p];
			return 0;
		}
		for(auto j : adj[p]) {
			if(d[j] <= d[p] + 1) continue;
			if(!ok(j, d[p]) && !ok(p, d[p] + 1)) continue;
			if(ok(j, d[p] + 1)) {
				st.erase({d[j], j});
				d[j] = d[p] + 1;
				st.insert({d[j], j});
			}
		}
		if(ok(p, d[p] + 1)) {
			d[p]++;
			st.insert({d[p], p});
		}
		if(tim > 1e7) break;
	}

	if(d[n] > 1e9) {
		cout<<"impossible";
		return 0;
	}

	cout<<d[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