Submission #428811

#	Time	Username	Problem	Language	Result	Execution time	Memory
428811		jangwonyoung	From Hacks to Snitches (BOI21_watchmen)	C++14	100 / 100	3311 ms	363412 KiB

watchmen

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=250005;
const int L=2755;
const int Z=1005;
int n,m,z,kk;
vector<int>adj[N];
int love[N],ssk[L];
int s[Z],l[Z],col[L],ord[L];

int e[L][L];
ll ed1[L][L],eb1[L][L];
ll d[L],b[L];


typedef pair<ll,pair<int,int> > plii;
priority_queue<plii,vector<plii>,greater<plii> >pq;
ll d1[N];
ll d2[L],b2[L];
ll d3[L][L],b3[L][L];
bool vis1[N];
bool vis2[L];
bool vis3[L][L];
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1; i<=m ;i++){
		int u,v;cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1; i<=n ;i++){
		adj[i].push_back(i);
		love[i]=-1;
	}
	cin >> z;
	for(int i=1; i<=z ;i++){
		cin >> l[i];
		s[i+1]=s[i]+l[i];
		for(int j=0; j<l[i] ;j++){
			int x;cin >> x;
			ssk[s[i]+j]=x;
			love[x]=s[i]+j;
			col[s[i]+j]=i;
			ord[s[i]+j]=j;
		}
	}
	/*for(int i=1; i<=n ;i++) cout << love[i] << ' ';
	cout << endl;
	for(int i=0; i<s[z+1] ;i++) cout << ssk[i] << ' ';
	cout << endl;*/
	kk=s[z+1];
	for(int i=1; i<=n ;i++){
		if(love[i]==-1) continue;
		for(auto c:adj[i]){
			if(love[c]!=-1) e[love[i]][love[c]]=1;
		}
	}
	for(int i=1; i<=z ;i++){
		for(int j=1; j<l[i] ;j++){
			e[s[i]+j][s[i]+j-1]=0;
		}
		e[s[i]][s[i]+l[i]-1]=0;
	}
	for(int i=1; i<=z ;i++){
		for(int j=1; j<=z ;j++){
			for(int k=0; k<l[j] ;k++){
				d[k]=1e18;
			}
			for(int k=l[i]-1; k>=0 ;k--){
				for(int h=l[j]; h>0 ;h--){
					d[h]=d[h-1]+1;b[h]=b[h-1];
				}
				d[0]=d[l[j]];b[0]=b[l[j]];
				for(int h=0; h<l[j] ;h++){
					if(!e[s[i]+k][s[j]+h]) continue;
					int nx=(1-h+l[j])%l[j];//distance-order
					d[nx]=1;b[nx]=h+s[j];
				}
			}
			for(int k=l[i]-1; k>=0 ;k--){
				for(int h=l[j]; h>0 ;h--){
					d[h]=d[h-1]+1;b[h]=b[h-1];
				}
				d[0]=d[l[j]];b[0]=b[l[j]];
				for(int h=0; h<l[j] ;h++){
					if(!e[s[i]+k][s[j]+h]) continue;
					int nx=(1-h+l[j])%l[j];//distance-order
					d[nx]=1;b[nx]=h+s[j];
				}
				for(int h=0; h<l[j] ;h++){
					ed1[s[i]+k][s[j]+h]=d[h];
					eb1[s[i]+k][s[j]+h]=b[h];
				}
			}
		}
	}
	for(int i=1; i<=n ;i++) d1[i]=1e18;
	for(int i=0; i<kk ;i++){
		d2[i]=1e18;
		for(int j=0; j<kk ;j++){
			d3[i][j]=1e18;
		}
	}
	d1[1]=0;
	pq.push({0,{1,1}});
	while(!pq.empty()){
		auto tmp=pq.top().se;pq.pop();
		if(tmp.fi==1){//only exists for non-guarded nodes
			int x=tmp.se;
			if(vis1[x]) continue;
			//cout << "d1 " << x << ' ' << d1[x] << endl;
			vis1[x]=true;
			for(auto c:adj[x]){
				if(love[c]==-1){
					if(d1[c]>d1[x]+1){
						d1[c]=d1[x]+1;
						pq.push({d1[c],{1,c}});	
					}
				}
				else if(love[x]==-1){
					int y=love[c];
					int i=col[y];
					int j=ord[y];
					{//move immediately
						if(j==(d1[x]+1)%l[i]);//cant move 
						else{
							int nx=s[i]+(d1[x]+1-j+l[i])%l[i];
							if(d2[nx]>d1[x]+1){
								d2[nx]=d1[x]+1;b2[nx]=y;
								pq.push({d2[nx],{2,nx}});	
							}
						}
					}
					{//wait until guard passed before enter
						ll wait=(j-d1[x])%l[i];
						wait=(wait+l[i])%l[i];
						int nx=s[i]+1;
						if(d2[nx]>d1[x]+wait+1){
							d2[nx]=d1[x]+wait+1;b2[nx]=y;
							pq.push({d2[nx],{2,nx}});
						}
					}
				}
				else if(col[love[x]]==col[love[c]] && ord[love[c]]==(ord[love[x]]+1)%l[col[love[x]]]){//walk on cycle
					if(d1[c]>d1[x]+1){
						d1[c]=d1[x]+1;
						pq.push({d1[c],{1,c}});	
					}
				}
			}
		}
		else if(tmp.fi==2){
			int x=tmp.se;
			if(vis2[x]) continue;
			//cout << "d2 " << x << ' ' << d2[x] << ' ' << b2[x] << endl;
			int y=b2[x];//where you actually at
			int i=col[y];
			
			vis2[x]=true;
			{//go to d1 without change in time
				int c=ssk[y];
				if(d1[c]>d2[x]){
					d1[c]=d2[x];
					pq.push({d1[c],{1,c}});
				}
			}
			{//go to d2 walking cycle in reverse direction
				if(x+2<s[i]+l[i]){
					int nx=x+2;
					if(d2[nx]>d2[x]+1){
						d2[nx]=d2[x]+1;b2[nx]=s[i]+(y-s[i]+l[i]-1)%l[i];
						pq.push({d2[nx],{2,nx}});	
					}
				}
			}
			{//go to d3
				for(int j=1; j<=z ;j++){
					for(int k=0; k<l[j] ;k++){
						int ny=(d2[x]+k)%l[j]+s[j];
						ll nd=d2[x]+ed1[y][k+s[j]];
						if(d3[x][ny]>d2[x]+ed1[y][k+s[j]]){
							d3[x][ny]=d2[x]+ed1[y][k+s[j]];
							b3[x][ny]=eb1[y][k+s[j]];
							pq.push({d3[x][ny],{3,x*L+ny}});
						}
					}
				}
			}
		}
		else{
			int x=tmp.se/L;
			int y=tmp.se%L;
			if(vis3[x][y]) continue;
			//cout << "d3 " << x << ' ' << y << ' ' << d3[x][y] << ' ' << b3[x][y] << endl;
			vis3[x][y]=true;
			int i=col[x];
			int j=col[y];
			{//go to d2
				if(y!=s[j]){
					if(d2[y]>d3[x][y]){
						d2[y]=d3[x][y];b2[y]=b3[x][y];
						pq.push({d2[y],{2,y}});
					}
				}
			}
			{
				int ny=(y-s[j]+l[i])%l[j]+s[j];
				if(d3[x][ny]>d3[x][y]+l[i]){
					d3[x][ny]=d3[x][y]+l[i];b3[x][ny]=b3[x][y];
					pq.push({d3[x][ny],{3,x*L+ny}});
				}
			}
		}
	}
	if(d1[n]==1e18) cout << "impossible\n";
	else cout << d1[n] << '\n';
}

Compilation message (stderr)

watchmen.cpp: In function 'int main()':
watchmen.cpp:184:10: warning: unused variable 'nd' [-Wunused-variable]
  184 |       ll nd=d2[x]+ed1[y][k+s[j]];
      |          ^~

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