Submission #1216180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216180		MuhammadSaram	Event Hopping (BOI22_events)	C++20	10 / 100	1599 ms	84140 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

const int M = 5000;

int dis[M][M],nx[M][M];

void bfs(int u)
{
	for (int i=0;i<M;i++) dis[u][i]=M;
	dis[u][u]=0;
	queue<int> q;
	q.push(u);
	while (!q.empty())
	{
		int x=q.front();q.pop();
		int cur=x;
		while (nx[x][cur]<M)
		{
			int i=nx[x][cur];
			if (dis[u][i]>dis[u][x]+1)
				dis[u][i]=dis[u][x]+1,q.push(i);
			cur=i;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int n,q;
	cin>>n>>q;
	if (n<=1000 && q<=100)
	{
		int s[n],e[n];
		for (int i=0;i<n;i++)
			cin>>s[i]>>e[i];
		for (int i=0;i<n;i++)
		{
			int p=i;
			for (int j=0;j<n;j++)
				if (i!=j && s[j]<=e[i] && e[i]<=e[j])
					nx[i][p]=j,p=j;
			nx[i][p]=M;
		}
		while (q--)
		{
			int s1,e1;
			cin>>s1>>e1;s1--,e1--;
			bfs(s1);
			if (dis[s1][e1]==M)
				cout<<"impossible"<<endl;
			else
				cout<<dis[s1][e1]<<endl;
		}
	}
	else if(n<=5000)
	{
		int s[n],e[n];
		for (int i=0;i<n;i++)
			cin>>s[i]>>e[i];
		for (int i=0;i<n;i++)
		{
			int p=i;
			for (int j=0;j<n;j++)
				if (i!=j && s[j]<=e[i] && e[i]<=e[j])
					nx[i][p]=j,p=j;
			nx[i][p]=M;
		}
		for (int i=0;i<n;i++)
			bfs(i);
		while (q--)
		{
			int s1,e1;
			cin>>s1>>e1;s1--,e1--;
			if (dis[s1][e1]==M)
				cout<<"impossible"<<endl;
			else
				cout<<dis[s1][e1]<<endl;
		}
	}
	else
	{
		
	}
	
	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