oj.uz

Submission #603226

# Submission time Handle Problem Language Result Execution time Memory
603226 2022-07-23T17:21:23 Z DanerZein Event Hopping (BOI22_events) C++14
20 / 100
 1500 ms 38428 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;
  bool t2=0;
  if(n<=1000 && q<=100) t2=1;
  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;
  }
  G.resize(n+1);
  if(t2){
    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);
	}
      }
    }
  }
  else{
    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;
      }
    }
    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);
      }
    }
  }
  while(q--){
    int s,e; cin>>s>>e;
    s--; e--;
    if(t2){
      bfs(s);
      if(dis[e]>=MAX) cout<<"impossible\n";
      else cout<<dis[e]<<endl;
    }
    else{
      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";
      }
    }
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 246 ms 27820 KB Output is correct
3 Correct 247 ms 27860 KB Output is correct
4 Correct 261 ms 28004 KB Output is correct
5 Correct 245 ms 27152 KB Output is correct
6 Correct 236 ms 26200 KB Output is correct
7 Correct 256 ms 25972 KB Output is correct
8 Correct 109 ms 19892 KB Output is correct
9 Correct 84 ms 18436 KB Output is correct
10 Correct 173 ms 25104 KB Output is correct
11 Correct 167 ms 23160 KB Output is correct
12 Correct 75 ms 22184 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 7 ms 388 KB Output is correct
6 Correct 12 ms 1108 KB Output is correct
7 Correct 18 ms 2004 KB Output is correct
8 Correct 19 ms 3028 KB Output is correct
9 Correct 78 ms 4408 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 7 ms 388 KB Output is correct
6 Correct 12 ms 1108 KB Output is correct
7 Correct 18 ms 2004 KB Output is correct
8 Correct 19 ms 3028 KB Output is correct
9 Correct 78 ms 4408 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 7 ms 340 KB Output is correct
15 Correct 9 ms 1108 KB Output is correct
16 Correct 19 ms 2004 KB Output is correct
17 Correct 19 ms 3028 KB Output is correct
18 Correct 78 ms 4308 KB Output is correct
19 Execution timed out 1544 ms 31128 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 7 ms 388 KB Output is correct
6 Correct 12 ms 1108 KB Output is correct
7 Correct 18 ms 2004 KB Output is correct
8 Correct 19 ms 3028 KB Output is correct
9 Correct 78 ms 4408 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 5 ms 404 KB Output is correct
14 Correct 6 ms 340 KB Output is correct
15 Correct 10 ms 1108 KB Output is correct
16 Correct 18 ms 2004 KB Output is correct
17 Correct 19 ms 3072 KB Output is correct
18 Correct 75 ms 4308 KB Output is correct
19 Correct 108 ms 28912 KB Output is correct
20 Execution timed out 1582 ms 22308 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 27908 KB Output is correct
2 Correct 233 ms 27916 KB Output is correct
3 Correct 274 ms 27864 KB Output is correct
4 Correct 87 ms 18424 KB Output is correct
5 Correct 174 ms 25268 KB Output is correct
6 Execution timed out 1585 ms 38428 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 246 ms 27820 KB Output is correct
3 Correct 247 ms 27860 KB Output is correct
4 Correct 261 ms 28004 KB Output is correct
5 Correct 245 ms 27152 KB Output is correct
6 Correct 236 ms 26200 KB Output is correct
7 Correct 256 ms 25972 KB Output is correct
8 Correct 109 ms 19892 KB Output is correct
9 Correct 84 ms 18436 KB Output is correct
10 Correct 173 ms 25104 KB Output is correct
11 Correct 167 ms 23160 KB Output is correct
12 Correct 75 ms 22184 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 7 ms 340 KB Output is correct
16 Correct 5 ms 340 KB Output is correct
17 Correct 7 ms 388 KB Output is correct
18 Correct 12 ms 1108 KB Output is correct
19 Correct 18 ms 2004 KB Output is correct
20 Correct 19 ms 3028 KB Output is correct
21 Correct 78 ms 4408 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 7 ms 340 KB Output is correct
25 Correct 5 ms 340 KB Output is correct
26 Correct 7 ms 340 KB Output is correct
27 Correct 9 ms 1108 KB Output is correct
28 Correct 19 ms 2004 KB Output is correct
29 Correct 19 ms 3028 KB Output is correct
30 Correct 78 ms 4308 KB Output is correct
31 Execution timed out 1544 ms 31128 KB Time limit exceeded
32 Halted 0 ms 0 KB -