Submission #581356

#	Time	Username	Problem	Language	Result	Execution time	Memory
581356		WongChun1234	From Hacks to Snitches (BOI21_watchmen)	C++14	5 / 100	180 ms	39168 KiB

watchmen

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=250050;
int n,m,u,v,k,l[N];
ll ans;
pair<int,int> incyc[N];
vector<int> adj[N],cyc[N];
vector<ll> dist[N];
vector<bool> final[N];
priority_queue<pair<ll,pair<int,int>>> dij;
int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++) incyc[i]={-1,-1},dist[i].resize(1),final[i].resize(1);
	for (int i=1;i<=m;i++){
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cin>>k;
	for (int i=1;i<=k;i++){
		cin>>l[i];
		cyc[i].resize(l[i]);
		for (int j=0;j<l[i];j++){
			cin>>cyc[i][j];
			dist[cyc[i][j]].resize(l[i]);
			final[cyc[i][j]].resize(l[i]);
			incyc[cyc[i][j]]={i,j};
		}
	}
	for (int i=1;i<=n;i++) for (auto &j:dist[i]) j=1e16;
	dist[1][0]=0;
	dij.push({0,{1,0}});
	while (dij.size()){
		pair<int,int> cnde=dij.top().second;
		dij.pop();
		if (final[cnde.first][cnde.second]) continue;
		//cerr<<cnde.first<<","<<cnde.second<<":"<<dist[cnde.first][cnde.second]<<endl;
		final[cnde.first][cnde.second]=1;
		for (auto i:adj[cnde.first]){
			if (incyc[i].first==-1){
				if (dist[i][0]>dist[cnde.first][cnde.second]+1){
					dist[i][0]=dist[cnde.first][cnde.second]+1;
					dij.push({-dist[i][0],{i,0}});
				}
			}else if (incyc[cnde.first].first==-1){
				//no cyc -> cyc
				for (int j=(dist[cnde.first][cnde.second]+1)%l[incyc[i].first];j<l[incyc[i].first];j++){
					if (j==incyc[i].second) continue;
					if (dist[i][j]>dist[cnde.first][cnde.second]+1+j-(dist[cnde.first][cnde.second]+1)%l[incyc[i].first]){
						dist[i][j]=dist[cnde.first][cnde.second]+1+j-(dist[cnde.first][cnde.second]+1)%l[incyc[i].first];
						dij.push({-dist[i][j],{i,j}});
					}
				}
				ll ndadd=l[incyc[i].first]-(dist[cnde.first][cnde.second]+1)%l[incyc[i].first];
				for (int j=0;j<(dist[cnde.first][cnde.second]+1)%l[incyc[i].first];j++){
					if (j==incyc[i].second) continue;
					if (dist[i][j]>dist[cnde.first][cnde.second]+j+ndadd){
						dist[i][j]=dist[cnde.first][cnde.second]+j+ndadd;
						dij.push({-dist[i][j],{i,j}});
					}
				}
			}else{
				//cyc -> cyc
				if ((dist[cnde.first][cnde.second]+1)%l[incyc[i].first]==incyc[i].second) continue;
				//cerr<<((dist[cnde.first][cnde.second])%l[incyc[i].first]==incyc[i].second)<<";"<<((incyc[i].second+1)%l[incyc[i].first]==incyc[cnde.first].second)<<"\n";
				if ((dist[cnde.first][cnde.second])%l[incyc[i].first]==incyc[i].second&&(incyc[i].second+1)%l[incyc[i].first]==incyc[cnde.first].second) continue;
				if (dist[i][(cnde.second+1)%l[incyc[i].first]]>dist[cnde.first][cnde.second]+1){
					dist[i][(cnde.second+1)%l[incyc[i].first]]=dist[cnde.first][cnde.second]+1;
					dij.push({-dist[i][(cnde.second+1)%l[incyc[i].first]],{i,(cnde.second+1)%l[incyc[i].first]}});
				}
			}
		}
	}
	ans=LLONG_MAX;
	for (auto i:dist[n]) ans=min(ans,i);
	cout<<ans<<"\n";
}

• Subtask 1: 5 / 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