Submission #1216181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216181		MuhammadSaram	Event Hopping (BOI22_events)	C++20	10 / 100	215 ms	14056 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define all(v) v.begin(), v.end()

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
	{
		int s[n],e[n],col[n],id[n]={};
		vector<vector<int>> v;
		for (int i=0;i<n;i++)
		{
			cin>>s[i]>>e[i];
			col[i]=i;
			v.push_back({s[i],i,1});
			v.push_back({e[i],i,0});
		}
		set<int> se;
		sort(all(v));
		for (auto v1:v)
		{
			if (v1[2]) se.insert(v1[1]);
			else
			{
				se.erase(v1[1]);
				if (!se.empty())
					col[*se.begin()]=col[v1[1]],id[*se.begin()]=id[v1[1]]+1;
			}
		}
		while (q--)
		{
			int s1,e1;
			cin>>s1>>e1;
			if (col[s1]==col[e1] && id[e1]>=id[s1])
				cout<<id[e1]-id[s1]<<endl;
			else
				cout<<"impossible"<<endl;
		}
	}
	
	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