Submission #1216172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216172		MuhammadSaram	Event Hopping (BOI22_events)	C++20	0 / 100	168 ms	736 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

const int M = 5000;

int dis[M][M],n;
vector<int> nei[M];

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int 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++)
			for (int j=0;j<n;j++)
				if (i!=j && s[j]<=e[i] && e[i]<=e[j])
					nei[i].push_back(j);
		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++)
			for (int j=0;j<n;j++)
				if (i!=j && s[j]<=e[i] && e[i]<=e[j])
					nei[i].push_back(j);
		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: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30