Submission #401012

#	Time	Username	Problem	Language	Result	Execution time	Memory
401012		errorgorn	From Hacks to Snitches (BOI21_watchmen)	C++17	70 / 100	6029 ms	524288 KiB

watchmen

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e)?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

int n,m,k;
vector<ii> edges;

const int EXT=1000000; //extra stuff for connecting 2 watchmen
vector<int> w[250005+EXT]; //period is implicit here
vector<int> al[250005+EXT];

priority_queue<iii,vector<iii>,greater<iii> > pq;
int upt[250005+EXT]; //time to update upwards

int id[250005+EXT]; //which watchmen
int bad[250005+EXT]; //when the watchmen comes
int ped[250005+EXT]; //period
int out[250005];

vector<ii> dial[10000005];

void read(int &x){
	x=0;
	char ch=getchar_unlocked();
	while (ch&16){
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
}

int fix(int i,int j){
	i%=j;
	if (i<0) i+=j;
	return i;
}

void upd(int k,int i,int j){
	if (w[i][j]>k){
		w[i][j]=k;
		//pq.push(iii(k,ii(i,j)));
		if (k>10000000) return;
		dial[k].pub(ii(i,j));
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	read(n),read(m);
	
	int a,b;
	rep(x,0,m){
		read(a),read(b);
		edges.pub(ii(a,b));
	}
	
	memset(ped,-1,sizeof(ped));
	memset(id,-1,sizeof(id));
	memset(bad,-1,sizeof(bad));
	
	read(k);
	rep(x,0,k){
		read(a);
		
		vector<int> path;
		rep(y,0,a){
			read(b);
			
			path.pub(b);
			bad[b]=y;
			id[b]=x;
			ped[b]=a;
			upt[b]=1;
		}
	}
	
	int IDX=n+1;
	
	rep(x,1,n+1) if (ped[x]!=-1){
		out[x]=IDX;
		al[x].pub(out[x]);
		IDX++;
	}
	
	for (auto &it:edges){
		tie(a,b)=it;
		if (id[a]>id[b]) swap(a,b);
		//cout<<id[a]<<" "<<id[b]<<endl;
		
		if (id[a]!=-1 && id[b]!=-1 && id[a]!=id[b]){
			al[a].pub(IDX);
			al[IDX].pub(b);
			ped[IDX]=ped[b];
			upt[IDX]=ped[a];
			IDX++;
			
			al[b].pub(IDX);
			al[IDX].pub(a);
			ped[IDX]=ped[a];
			upt[IDX]=ped[b];
			IDX++;
		}
		else if (id[a]==-1 && id[b]!=-1){
			al[a].pub(b);
			al[out[b]].pub(a);
		}
		else{
			al[a].pub(b);
			al[b].pub(a);
		}
	}
	
	rep(x,0,IDX){
		if (ped[x]==-1) w[x].pub(1e9);
		else{
			rep(y,0,ped[x]) w[x].pub(1e9);
		}
	}
	
	upd(0,1,0);
	
	int weight=0;
	while (weight<10000000){
		if (dial[weight].empty()){
			weight++;
			continue;
		}
		
		int n1,n2;
		tie(n1,n2)=dial[weight].back();
		dial[weight].pob();
		
		if (w[n1][n2]!=weight) continue;
		if (ped[n1]!=-1 && weight%ped[n1]==bad[n1]) continue;
		//same position as watchmen
		
		if (n1==n){
			cout<<weight<<endl;
			return 0;
		}
		
		//cout<<weight<<" "<<n1<<" "<<n2<<" "<<ped[n1]<<" "<<bad[n1]<<endl;
		
		for (auto it:al[n1]){
			if (ped[it]==-1){ //this is a problem....
				int ww=weight;
				if (n1<=n) ww++;
				upd(ww,it,0);
			}
			else if (ped[n1]==-1 && ped[it]!=-1){ //update all
				// we have to optmize this part...
				int ww=weight+1;
				upd(ww,it,ww%ped[it]);
				
				//also need one that lands immediately after watchmen pass
				ww=weight+fix(bad[it]-weight,ped[it])+1;
				//cout<<weight<<" "<<ww<<" "<<ped[it]<<" "<<bad[it]<<endl;
				upd(ww,it,ww%ped[it]);
			}
			else if (id[n1]==id[it]){
				int ww=weight+1;
				
				if ((bad[it]+1)%ped[it]==bad[n1] && ww%ped[it]==bad[n1]) continue;
				upd(ww,it,ww%ped[it]);
			}
			else{
				int ww=weight;
				if (n1<=n) ww++;
				
				upd(ww,it,ww%ped[it]);
			}
		}
		
		if (ped[n1]!=-1){
			int ww=weight+upt[n1];
			upd(ww,n1,ww%ped[n1]);
		}
	}
	
	
	/*
	rep(x,1,IDX){
		cout<<x<<": ";
		for (auto &it:w[x]) cout<<it<<" "; cout<<endl;
	}
	//*/
	
	cout<<"impossible"<<endl;
}

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