제출 #406259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
406259		oolimry	From Hacks to Snitches (BOI21_watchmen)	C++17	35 / 100	4448 ms	195060 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;
typedef long long lint;
typedef pair<int, int> ii;

int mod[250005];
int rem[250005];
int label[250005];
int basic[250005];
int looped[250005];
int best[250005];

vector<int> adj[250005];
vector<int> special[250005];
 
vector<int> dis[250005];
 
vector<ii> Q[2000005];

int uu[3000005];
int vv[3000005];
void addedge(int u, int v){
	if(label[v] == 0) adj[u].push_back(v);
	else special[u].push_back(v);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	//freopen("i.txt","r",stdin);
	
	int n, m; cin >> n >> m;
	for(int i = 1;i <= m;i++){
		cin >> uu[i] >> vv[i];
	}
	
	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 <= m;i++){
		addedge(uu[i], vv[i]);
		addedge(vv[i], uu[i]);
	}
	
	const int inf = 102345678;
	for(int i = 1;i <= n;i++){
		dis[i].resize(mod[i]);
		fill(all(dis[i]), inf);
		best[i] = inf;
	}
 
	Q[0].push_back(ii(1,0));
	dis[1][0] = 0; 
	for(int d = 0;d <= 1400000;d++){
		for(ii u : Q[d]){
			 int a = u.first, b = u.second;
			 if(d % mod[a] == rem[a]){
				 dis[a][b] = 0;
				 continue;
			 }
			 if(dis[a][b] != d) continue;
			 dis[a][b] = d;
			 best[a] = min(best[a], d);
			 
			 for(int v : special[a]){
				 if(looped[v]) continue;
				 for(int r = 1;r <= mod[v];r++){
					 if(mod[a] != 1 and (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] > d+r and best[v] > d+r-mod[v] and rr != rem[v]){
								dis[v][rr] = d+r;
								Q[d+r].push_back(ii(v, rr));
							}
						 }
						 break;
					 }
					int rr = (d+r)%mod[v];
					if(dis[v][rr] > d+r and best[v] > d+r-mod[v] and rr != rem[v]){
						dis[v][rr] = d+r;
						Q[d+r].push_back(ii(v, rr));
					}
					if(rr == rem[v]+1 or rr == rem[v]+1-mod[v]) break;
					if(label[v] == 0 or label[a] == label[v]) break;
				 }
				 if(label[a] == 0) looped[v] = true;
			 }
			 
			 if(basic[a]) continue;
			 basic[a] = 1;
			 
			 for(int v : adj[a]){
				 if(dis[v][0] > d+1){
					dis[v][0] = d+1;
					Q[d+1].push_back(ii(v, 0));
				}
			 }
		}
		Q[d].clear();
	}
	
	cout << dis[n][0];
}

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