Submission #896419

#	Time	Username	Problem	Language	Result	Execution time	Memory
896419		Nexus	Event Hopping (BOI22_events)	C++17	0 / 100	1556 ms	295132 KiB

events

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <math.h>
#include <string>
#include <algorithm>
#include <random>
#include <iomanip>
#include <utility>
#include <cstring>
//#include <bits/stdc++.h>

#define ll long long

using namespace std;

const ll N=1e3+9,M=1e18+9,mod=1e9+7;
//cout<<fixed<<setprecision(6)<<

ll dp[N][N],s[N],e[N],n,q,i,j,k,ans;
bool vis[N];
vector<ll>v[N];

void dfs(ll node,ll num){
	if(node==j){
		k=1,ans=min(ans,num);
  	  return;
	}
	if(vis[node])return;
	vis[node]=1;
	for(auto p:v[node]){
      ll g=k;
      dfs(p,num+1);
      if(!g && k)dp[node][j]=ans-num;
    }
	vis[node]=0;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	
	cin>>n>>q;
	for(i=1;i<=n;++i)cin>>s[i]>>e[i];
	for(ll i=1;i<=n;++i){
		for(ll j=1;j<=n;++j){
			if(s[j]<=e[i] && e[i]<=e[j])
			v[i].push_back(j);
		}
	}
	while(q--){
		cin>>i>>j;
		k=0,ans=M;
      if(dp[i][j])cout<<dp[i][j]<<'\n';else{
		dfs(i,0);
		if(k)cout<<ans<<'\n';
		else cout<<"impossible\n";}
	}
}

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