Submission #1187881

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

watchmen

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

#define int long long int

#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);
vi nxt(maxn,-1),prv(maxn,-1);
vi tme(maxn,-1);
vi mods(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);
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	//freopen("test.txt","r",stdin);
	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);
		for (int j=0; j<l; j++) {
			cin >> a;
			tme[--a]=j;
			mods[a]=l;
			cyc[j]=a;
		}
		int prvv=l-1;
		while (graph[cyc[prvv]].size()==2) {
			prvv--;
		}
		for (int j=0; j<l; j++) {
			if (graph[cyc[j]].size()==2) {
				continue;
			}
			prv[cyc[j]]=cyc[prvv];
			nxt[cyc[prvv]]=cyc[j];
			prvv=j;
		}
	}
	vl len(n,1e18);
	len[0]=0;
	priority_queue<pl,vector<pl>,greater<pl>> q;
	q.push({0,0});
	while (q.size()) {
		auto [t,cur]=q.top();
		q.pop();
		if (len[cur]!=t) {
			continue;
		}
		if (cur==n-1) {
			cout << t << '\n';
			return 0;
		}
		for (auto to:graph[cur]) {
			if (tme[to]!=-1 && tme[cur]!=-1) {
				continue;
			}
			ll newt=t+1+(tme[to]!=-1 && (t+1)%mods[to]==tme[to]);
			if (newt<len[to]) {
				len[to]=newt;
				q.push({newt,to});
			}
		}
		if (tme[cur]==-1) {
			continue;
		}
		int newt=t+(tme[nxt[cur]]-tme[cur]+mods[cur])%mods[cur];
		if (newt<len[nxt[cur]]) {
			len[nxt[cur]]=newt;
			q.push({newt,nxt[cur]});
		}
		newt=t+(tme[cur]-tme[prv[cur]]+mods[cur])%mods[cur];
		ll strt=tme[prv[cur]];
		ll nd=tme[cur];
		ll strt2=t%mods[cur];
		ll nd2=newt%mods[cur];
		if (inter(strt,nd,strt2,nd2,mods[cur])) {
			ll add=(tme[cur]+1-strt2+mods[cur])%mods[cur];
			newt+=add;
			strt2=(strt2+add)%mods[cur];
			nd2=(nd2+add)%mods[cur];
		}
		if (inter(strt,nd,strt2,nd2,mods[cur])) {
			continue;
		}
		if (newt<len[prv[cur]]) {
			len[prv[cur]]=newt;
			q.push({newt,prv[cur]});
		}
	}
	assert(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