제출 #1174168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174168		JuanJL	Event Hopping (BOI22_events)	C++20	10 / 100	1599 ms	150800 KiB

events

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#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 int ll;

const int MAXN = 5000+4;

vector<ll> adj[MAXN];

ll n;

ll dijkstra(ll start, ll end){
	vector<ll> cost(n,-1);
	vector<bool> visit(n,false);
	
	priority_queue<pair<ll,ll>> pq;
	pq.push({0,start});
	
	while(!pq.empty()){
		ll nd = pq.top().snd;
		ll cst = pq.top().fst*-1;
		pq.pop();
		
		if(visit[nd]) continue;
		visit[nd]=true;
		cost[nd]=cst;
		
		for(auto i:adj[nd]){
			pq.push({(cst+1)*-1,i});
		}
	}
	
	return cost[end];
}

ll rcost[MAXN][MAXN];

void bfs(ll start){
	//vector<ll> cost(n+1,-1);
	//vector<bool> visit(n,false);
	
	
	queue<pair<ll,ll>> cola;
	cola.push({start,n});
	//cost[n]=-1;
	
	while(!cola.empty()){
		ll nd = cola.front().fst;
		ll p = cola.front().snd;
		cola.pop();
		if(rcost[start][nd]!=-1) continue;
		rcost[start][nd]=rcost[start][p]+1;
		//cout<<cost[nd]<<" "<<nd<<'\n';
		for(auto i:adj[nd]) if(rcost[start][i]==-1){
			cola.push({i,nd});
		}
	}
	//forn(i,0,n) rcost[start][i]=cost[i];
	//return cost[end];
}

int main(){ FIN;
	mset(rcost,-1);
	ll q; cin>>n>>q;
	
	vector<pair<ll,ll>> r(n); forn(i,0,n) cin>>r[i].fst>>r[i].snd;
	
	vector<pair<pair<ll,ll>,ll>> psr; // { { point, type } , ind }
	forn(i,0,n){
		psr.pb({{r[i].fst,0},i});
		psr.pb({{r[i].snd,1},i});
	}
	sort(ALL(psr));
	
	set<ll> s;
	
	queue<pair<ll,ll>> cola;
	forn(i,0,SZ(psr)){
		
		while(!cola.empty()&&cola.front().fst<psr[i].fst.fst){
			s.erase(s.find(cola.front().snd));
			cola.pop();
		}
		
		if(psr[i].fst.snd==0){
			s.insert(psr[i].snd);
		}else{
			//s.erase(s.find(psr[i].snd));
			cola.push(pair<ll,ll>({psr[i].fst.fst,psr[i].snd}));
			for(auto j:s) if(psr[i].snd!=j){
				adj[psr[i].snd].pb(j);
				//radj[j].pb(psr[i].snd);
			}
		}
	}
	
	forn(i,0,q){
		ll s,e; cin>>s>>e; s--; e--;
		if(rcost[s][s]==-1) bfs(s);
		ll res = rcost[s][e];
		if(res==-1) cout<<"impossible\n";
		else cout<<res<<'\n';
	}
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30