Submission #1187492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187492		kl0989e	From Hacks to Snitches (BOI21_watchmen)	C++17	0 / 100	49 ms	27464 KiB

watchmen

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

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=250000+10;

vector<vi> graph(maxn);
vector<vector<array<int,4>>> nxt(maxn),prv(maxn);
vi tme(maxn,-1);

bool inter(ll a, ll b, ll c, ll d, ll mod) {
	if (b<a) {
		return inter(0,b,c,d,mod)|inter(a,mod-1,c,d,mod);
	}
	else if (d<c) {
		return inter(a,b,0,d,mod)|inter(a,b,c,mod-1,mod);
	}
	return (a<=d && c<=b);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n,m;
	cin >> n >> m;
	int a,b;
	for (int i=0; i<m; i++) {
		cin >> a >> b;
		graph[--a].pb(--b);
		graph[b].pb(a);
	}
	int k;
	cin >> k;
	int l;
	for (int i=0; i<k; i++) {
		cin >> l;
		vi cyc(l);
		vector<array<int,3>> ord;
		for (int j=0; j<l; j++) {
			cin >> a;
			tme[--a]=j;
			cyc[j]=a;
		}
		if (l==1) {
			continue;
		}
		for (int i=0; i<l; i++) {
			a=cyc[i];
			for (auto to:graph[a]) {
				if (tme[to]!=-1) {
					continue;
				}
				ord.pb({to,tme[a],l});
			}
		}
		for (int j=0; j<ord.size(); j++) {
			array<int,4> t;
			t[0]=ord[(j+1)%ord.size()][0];
			t[1]=ord[(j+1)%ord.size()][1];
			t[2]=ord[(j+1)%ord.size()][2];
			t[3]=ord[j][1];
			nxt[ord[j][0]].pb(t);
			t[0]=ord[(j-1+ord.size())%ord.size()][0];
			t[1]=ord[(j-1+ord.size())%ord.size()][1];
			t[2]=ord[(j-1+ord.size())%ord.size()][2];
			prv[ord[j][0]].pb(t);
		}
	}
	vector<vl> len(n,vl(2,1e18));
	len[0][0]=0;
	priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> q;
	q.push({0,0,0});
	while (q.size()) {
		array<ll,3> temp=q.top();
		q.pop();
		ll t=temp[0],cur=temp[1],on_cyc=temp[2];
		if (len[cur][on_cyc]!=t) {
			continue;
		}
		if (cur==n-1) {
			cout << t << '\n';
			return 0;
		}
		for (auto [to,ind,mod,curind]:nxt[cur]) {
			ll newt=t+1-on_cyc;
			newt+=(newt%mod==curind)+(ind-curind+mod)%mod+1-on_cyc;
			if (newt<len[to][0]) {
				len[to][0]=newt;
				q.push({newt,to,0});
			}
			if (newt<len[to][1]) {
				len[to][1]=newt;
				q.push({newt,to,0});
			}
		}
		for (auto [to,ind,mod,curind]:prv[cur]) {
			ll newt=t+2-2*on_cyc+(curind-ind+mod)%mod;
			ll strt=ind;
			ll nd=curind;
			ll strt2=(t+1-on_cyc)%mod;
			ll nd2=(newt-1)%mod;
			if (inter(strt,nd,strt2,nd2,mod)) {
				ll add=(curind+1-strt2+mod)%mod;
				newt+=add;
				strt2=(strt2+add)%mod;
				nd2=(nd2+add)%mod;
			}
			if (inter(strt,nd,strt2,nd2,mod)) {
				newt=1e9;
			}
			if (newt<len[to][0]) {
				len[to][0]=newt;
				q.push({newt,to,0});
			}
			if (newt<len[to][1]) {
				len[to][1]=newt;
				q.push({newt,to,0});
			}
		}
		if (on_cyc) {
			continue;
		}
		for (auto to:graph[cur]) {
			if (tme[to]!=-1) {
				continue;
			}
			if (t+1<len[to][0]) {
				len[to][0]=t+1;
				q.push({t+1,to,0});
			}
		}
	}
	cout << "impossible\n";
  return 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