oj.uz

Submission #603225

# Submission time Handle Problem Language Result Execution time Memory
603225 2022-07-23T17:19:17 Z DanerZein Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 39012 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
const int MAX_N=1e5+10;
const int MAX=1e9;
vector<vi> G;
vii ev;
int dis[MAX_N];
int n;
bool isq[MAX_N];
void bfs(int u){
  for(int i=0;i<n;i++) dis[i]=MAX;
  dis[u]=0; isq[u]=1;
  queue<int> q; q.push(u);
  while(!q.empty()){
    int x=q.front(); q.pop();
    isq[x]=0;
    for(auto &v:G[x]){
      if(dis[v]>dis[x]+1){
	dis[v]=dis[x]+1;
	if(!isq[v]){
	  isq[v]=1;
	  q.push(v);
	}
      }
    }
  }
}
int in[MAX_N];
int pa[MAX_N][32];
int le[MAX_N];
void dfs(int u,int p){
  pa[u][0]=p;
  for(int i=1;i<=20;i++){
    pa[u][i]=pa[pa[u][i-1]][i-1];
  }
  for(auto &v:G[u]){
    if(v!=p) {
      le[v]=le[u]+1;
      dfs(v,u);
    }
  }
}
int father(int u,int v){
  int dif=le[u]-le[v];
  if(dif<0) return -1;
  for(int i=0;i<=20;i++){
    if(dif&(1<<i)) u=pa[u][i];
  }
  if(u!=v) return -1;
  return dif;
}
int con[MAX_N];
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int q; cin>>n>>q;
  vii enp;
  for(int i=0;i<n;i++){
    int a,b; cin>>a>>b;
    ev.push_back(ii(a,b));
    enp.push_back(ii(b,i));
    con[i]=i;
  }
  sort(enp.begin(),enp.end());
  for(int i=0;i<n-1;i++){
    if(enp[i].first==enp[i+1].first){
      con[enp[i].second]=enp[i+1].second;
      con[enp[i+1].second]=enp[i].second;
    }
  }
  G.resize(n+1);
  for(int i=0;i<n;i++){
    auto it=lower_bound(enp.begin(),enp.end(),ii(ev[i].first,0));
    int l=it-enp.begin();
    it=upper_bound(enp.begin(),enp.end(),ii(ev[i].second+1,0));
    int r=it-enp.begin();
    for(int j=l;j<r;j++){
      if(i!=enp[j].second){
	G[i].push_back(enp[j].second);
	in[enp[j].second]=1;
      }
    }
  }
  for(int i=0;i<n;i++){
    if(!in[i] || con[i]!=i){
      dfs(i,i);
    }
  }
  /*
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(ev[j].first<=ev[i].second && ev[i].second<=ev[j].second){
	G[i].push_back(j);
      }
    }
    }*/
  while(q--){
    int s,e; cin>>s>>e;
    s--; e--;
    int ans=father(s,e);
    if(ans!=-1) cout<<ans<<endl;
    else{
      int ca=father(s,con[e])+1;
      if(ca!=0) cout<<ca<<endl;
      else
      cout<<"impossible\n";
    }
      /*bfs(s);
    if(dis[e]>=MAX) cout<<"impossible\n";
    else cout<<dis[e]<<endl;*/ 
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 255 ms 29636 KB Output is correct
3 Correct 296 ms 29692 KB Output is correct
4 Correct 279 ms 29688 KB Output is correct
5 Correct 294 ms 29728 KB Output is correct
6 Correct 237 ms 28820 KB Output is correct
7 Correct 312 ms 28760 KB Output is correct
8 Correct 119 ms 22604 KB Output is correct
9 Correct 94 ms 21176 KB Output is correct
10 Correct 222 ms 27856 KB Output is correct
11 Correct 208 ms 26060 KB Output is correct
12 Correct 80 ms 24436 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 28436 KB Output is correct
2 Correct 250 ms 28388 KB Output is correct
3 Correct 315 ms 28444 KB Output is correct
4 Correct 92 ms 18816 KB Output is correct
5 Correct 185 ms 25632 KB Output is correct
6 Execution timed out 1530 ms 39012 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 255 ms 29636 KB Output is correct
3 Correct 296 ms 29692 KB Output is correct
4 Correct 279 ms 29688 KB Output is correct
5 Correct 294 ms 29728 KB Output is correct
6 Correct 237 ms 28820 KB Output is correct
7 Correct 312 ms 28760 KB Output is correct
8 Correct 119 ms 22604 KB Output is correct
9 Correct 94 ms 21176 KB Output is correct
10 Correct 222 ms 27856 KB Output is correct
11 Correct 208 ms 26060 KB Output is correct
12 Correct 80 ms 24436 KB Output is correct
13 Incorrect 0 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -