제출 #1216232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216232		Muhammad_Aneeq	Event Hopping (BOI22_events)	C++20	0 / 100	1595 ms	8636 KiB

events

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
int const N=1e5+10;
int n,q;
int dist[N]={};
vector<int>nei[N]={};
void bfs(int s,int e)
{
	queue<int>Q;
	for (int i=1;i<=n;i++)
		dist[i]=1e9+10;
	dist[s]=0;
	Q.push(s);
	while (Q.size())
	{
		int z=Q.front();
		Q.pop();
		for (auto i:nei[z])
		{
			if (dist[i]>dist[z]+1)
			{
				dist[i]=dist[z]+1;
				Q.push(i);
			}
		}
	}
}
inline void solve()
{
	cin>>n>>q;
	int l[n+1],r[n+1];
	vector<pair<int,int>>seg;
	for (int i=1;i<=n;i++)
	{
		cin>>l[i]>>r[i];	
		seg.push_back({l[i],-i});
		seg.push_back({r[i],i});
	}
	sort(begin(seg),end(seg));
	set<int>s;
	for (int i=0;i<seg.size();i++)
	{
		int j=i;
		while (j<seg.size()&&seg[j].first==seg[i].first)
		{
			if (seg[j].second<0)
				s.insert(-seg[j].second);
			else
			{
				for (auto k:s)
				{
					if (k!=seg[j].second)
						nei[seg[j].second].push_back(k);
				}
			}
			j++;
		}
		j--;
		for (int l=i;l<=j;l++)
		{
			if (seg[j].second>0)
				s.erase(seg[j].second);
		}
		i=j;
	}
	while (q--)
	{
		int s,e;
		cin>>s>>e;
		bfs(s,e);
		if (dist[e]==1e9+10)
			cout<<"impossible\n";
		else
			cout<<dist[e]<<endl;
	}
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

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