Submission #406095

#	Time	Username	Problem	Language	Result	Execution time	Memory
406095		oolimry	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	739 ms	524288 KiB

watchmen

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
#define l first
#define r second
typedef long long lint;
typedef pair<lint, lint> ii;

lint mod[250005];
lint rem[250005];
lint label[250005];

vector<int> dis[250005];
vector<int> adj[250005];

vector<ii> Q[2000005];
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, m; cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for(int i = 1;i <= n;i++) mod[i] = 1, rem[i] = 1;
	int K; cin >> K;
	for(int i = 1;i <= K;i++){
		int L; cin >> L;
		for(int u = 0;u < L;u++){
			int x; cin >> x;
			mod[x] = L;
			rem[x] = u;
			label[x] = i;
		}
	}
	
	for(int i = 1;i <= n;i++){
		dis[i].resize(mod[i]);
		fill(all(dis[i]), -1);
	}
	
	Q[0].push_back(ii(1,0));
	for(int d = 0;d <= 1900000;d++){
		for(ii u : Q[d]){
			 int a = u.first, b = u.second;
			 if(dis[a][b] != -1) continue;
			 if(d % mod[a] == rem[a]) continue;
			// show3(a,b,d);
			 dis[a][b] = d;
			 for(int v : adj[a]){
				 
				 for(int r = 1;r <= mod[v];r++){
					 if(a == 3 and d == 2 and b == 2 and v == 4) show(r);
					 if((d+r)%mod[a] == rem[a]){
						 if(a == 3 and d == 2 and b == 2 and v == 4) show2(rem[v], rem[a]);
						 if(rem[v] == (rem[a]+1)%mod[v] or label[a] != label[v]){
							Q[d+r].push_back(ii(v, (d+r)%mod[v]));
						 }
						 break;
					 }
					 Q[d+r].push_back(ii(v, (d+r)%mod[v]));
				 }
			 }
		}
		Q[d].clear();
	}
	
	cout << dis[n][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