Submission #1199898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199898		JuanJL	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	2092 ms	2528 KiB

Main

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll;

const int MAXN = 300+5;

ll n,k,m;

ll a[MAXN];
ll b[MAXN];
vector<ll> op[MAXN];

bool inRange(ll p, ll a, ll b){
	if(a<b){ // iz a de
		if(a<=p && a+k>=p) return true;
	}else{
		if(a>=p && a-k<=p) return true;
	}
	return false;
}

ll next(ll p, ll a, ll b){
	if(a<b){ // iz a de
		if(p+1<=b) return p+1;
	}else{
		if(p-1>=b) return p-1;
	}
	return -1;
}

ll bfs( ll pini , ll pfin ){
	
	//[][] nd y linea
	bool vis[MAXN][MAXN]; mset(vis,false);
	ll dis[MAXN][MAXN];  mset(dis,-1);
	
	queue< pair< ll , pair<ll,ll> > > q;
	
	for(auto i:op[pini]) q.push({1,{pini,i}});
	
	
	
	while(!q.empty()){
		ll nd = q.front().snd.fst;
		ll line = q.front().snd.snd;
		ll cost = q.front().fst;
		
		q.pop();
		
		if(vis[nd][line]) continue;
		
		//cout<<nd<<" "<<line<<" "<<cost<<'\n';
		
		vis[nd][line]=true;
		dis[nd][line]=cost;
		
		if(next(nd,a[line],b[line])!=-1){
			q.push({(cost),{next(nd,a[line],b[line]),line}});
		}
		
		for(auto i:op[nd]) q.push({cost+1,{nd,i}});
		
	}
	
	ll res = MAXN;
	forn(i,0,m){
		if(vis[pfin][i]){
			res=min(res,dis[pfin][i]);
		}
	}
	
	if(res==MAXN) return -1;
	
	return res;
}

int main(){ FIN;

	cin>>n>>k>>m; k--;
	
	forn(i,0,m) cin>>a[i]>>b[i];
	
	forn(p,0,n+1){
		forn(i,0,m){
			if(inRange(p,a[i],b[i])) op[p].pb(i);
		}
	}
	
	ll q; cin>>q;
	
	while(q--){
	
		ll ini,fin; cin>>ini>>fin;
		
		cout<<bfs(ini,fin)<<'\n';
		
	}

	return 0;	
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13