Submission #406112

#	Time	Username	Problem	Language	Result	Execution time	Memory
406112		oolimry	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	1345 ms	524292 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<int, int> ii;

int mod[250005];
int rem[250005];
int label[250005];

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

vector<ii> Q[500005];
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 <= 4000;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((d+r)%mod[a] == rem[a]){
						 if(rem[v] == (rem[a]+1)%mod[v] or label[a] != label[v]){
							
							int rr = (d+r)%mod[v];
							if(dis[v][rr] == -1) Q[d+r].push_back(ii(v, (d+r)%mod[v]));
						 }
						 break;
					 }
					int rr = (d+r)%mod[v];
					if(dis[v][rr] == -1) 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