제출 #1216192

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

events

#include <bits/stdc++.h>

using namespace std;

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

const int M = 5000, M1 = 1e5, lg = 17;

int dis[M][M],nx[M][M];
vector<int> nei[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 dep[M], par[M][lg];
bool vis[M];

void dfs(int u)
{
	vis[u]=1;
	for (int p=1;(1<<p)<=dep[u];p++)
		par[u][p]=par[par[u][p-1]][p-1];
	for (int i:nei[u])
		par[i][0]=u,dep[i]=dep[u]+1,dfs(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],ts[n]={};
		map<int,vector<pair<int,int>>> mp;
		for (int i=0;i<n;i++)
		{
			cin>>s[i]>>e[i];
			mp[s[i]].push_back({i,1});
			mp[e[i]].push_back({i,0});
		}
		set<int> se;
		set<pair<int,int>> se1;
		for (auto [x,y]:mp)
		{
			int cnt=0;
			for (auto [i,j]:y)
				cnt+=1-j;
			if (cnt==2)
			{
				int f=-1;
				for (auto [i,j]:y)
					if (!j)
					{
						if (~f)
						{
							if (ts[f])
								nei[i].push_back(f),se1.insert({f,i});
							else if(ts[i])
								nei[f].push_back(i),se1.insert({i,f});
							else
								se1.insert({i,f}),se1.insert({f,i});
						}
						else f=i;
					}
			}
			else if(cnt==1)
			{
				int u;
				for (auto [i,j]:y) if (!j) u=i;
				se.erase(u);
				if (!se.empty())
					nei[*se.begin()].push_back(u),ts[*se.begin()]=1;
			}
			for (auto [i,j]:y)
				if (j) se.insert(i);
				else se.erase(i);
		}
		for (auto [x,y]:mp)
		{
			for (auto [i,j]:y)
				if (!j && !vis[i])
					dfs(i);
		}
		while (q--)
		{
			int s1,e1;
			cin>>s1>>e1;
			if (se1.count({s1,e1}))
				cout<<1<<endl;
			else if(dep[s1]>=dep[e1])
			{
				int dif=dep[s1]-dep[e1];
				for (int p=0;p<lg;p++)
					if (dif>>p&1)
						s1=par[s1][p];
				if (s1==e1)
					cout<<dif<<endl;
				else
					cout<<"impossible"<<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