Mario

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

const int inf=1e9;

int l[111];
int r[111];

int d[111];
int u[111];

pair<int, int> get(int t, int i){
	if (t%(2*(r[i]-l[i]))<(r[i]-l[i])){
		return {l[i]+t%(2*(r[i]-l[i])), 1};
	}
	else{
		return {r[i]-(t+r[i]-l[i])%(2*(r[i]-l[i])), -1};
	}
}

int when(int a, int b, int lb, int ub){
	if (r[a]<l[b]) return inf;
	if (r[b]<l[a]) return inf;
	ub=min(ub, lb+4*max(r[a]-l[a], r[b]-l[b])*min(r[a]-l[a], r[b]-l[b])/__gcd(r[a]-l[a], r[b]-l[b]));
	auto ma=get(lb, a);
	auto mb=get(lb, b);
	for (int it=lb;it<=ub;it++){
		if (ma.F==mb.F) return it;
		
		ma.F+=ma.S;
		mb.F+=mb.S;
		
		if (ma.F>r[a]){
			ma.F-=2;
			ma.S=-1;
		}
		else if(ma.F<l[a]){
			ma.F+=2;
			ma.S=1;
		}
		
		if (mb.F>r[b]){
			mb.F-=2;
			mb.S=-1;
		}
		else if(mb.F<l[b]){
			mb.F+=2;
			mb.S=1;
		}
	}
	return inf;
}

void solve(){
	int n,w;
	cin>>n>>w;
	w*=2;
	priority_queue<pair<int, int> > dij;
	for (int i=0;i<n;i++){
		d[i]=inf;
		u[i]=0;
		cin>>l[i]>>r[i];
		l[i]*=2;
		r[i]*=2;
		if (l[i]==0){
			d[i]=0;
			dij.push({0, i});
		}
	}
	int ans=inf;
	while (!dij.empty()){
		auto t=dij.top();
		dij.pop();
		int dd=-t.F;
		int x=t.S;
		if (u[x]) continue;
		u[x]=1;
		assert(dd==d[x]);
		if (r[x]==w){
			int cp=(dd+(r[x]-l[x]))%(2*(r[x]-l[x]));
			ans=min(ans, dd+2*(r[x]-l[x])-cp);
		}
		for (int i=0;i<n;i++){
			if (u[i]==0){
				int itr=when(x, i, dd, min(d[i]-1, ans));
				if (itr==inf) continue;
				assert(itr<d[i]);
				d[i]=itr;
				dij.push({-d[i], i});
			}
		}
	}
	if (ans==inf) cout<<"IMPOSSIBLE\n";
	else cout<<ans/2<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++){
		solve();
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED