oj.uz

Submission #603799

# Submission time Handle Problem Language Result Execution time Memory
603799 2022-07-24T11:53:30 Z DanerZein Event Hopping (BOI22_events) C++14
20 / 100
 1500 ms 40688 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 MIN_N=5010;
const int MAX_N=1e5+10;
const int MAX=1e9;
vector<vi> G;
vii ev;
int dis[MIN_N][MIN_N];
int ans[MAX_N];
int n;
bool isq[MAX_N];
void bfs(int u){
  for(int i=0;i<n;i++) dis[u][i]=MAX;
  dis[u][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[u][v]>dis[u][x]+1){
	dis[u][v]=dis[u][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<=5000) 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);
	}
      }
    }
    for(int i=0;i<n;i++) bfs(i);
  }
  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){
      if(dis[s][e]>=MAX) cout<<"impossible\n";
      else cout<<dis[s][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 0 ms 340 KB Output is correct
2 Correct 307 ms 30960 KB Output is correct
3 Correct 284 ms 31000 KB Output is correct
4 Correct 341 ms 30884 KB Output is correct
5 Correct 292 ms 30124 KB Output is correct
6 Correct 292 ms 29228 KB Output is correct
7 Correct 341 ms 29020 KB Output is correct
8 Correct 115 ms 23016 KB Output is correct
9 Correct 90 ms 21468 KB Output is correct
10 Correct 241 ms 28184 KB Output is correct
11 Correct 229 ms 26212 KB Output is correct
12 Correct 89 ms 24436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 24 ms 8316 KB Output is correct
4 Correct 16 ms 8256 KB Output is correct
5 Correct 24 ms 8268 KB Output is correct
6 Correct 52 ms 9060 KB Output is correct
7 Correct 146 ms 9940 KB Output is correct
8 Correct 184 ms 10924 KB Output is correct
9 Correct 890 ms 12292 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 24 ms 8316 KB Output is correct
4 Correct 16 ms 8256 KB Output is correct
5 Correct 24 ms 8268 KB Output is correct
6 Correct 52 ms 9060 KB Output is correct
7 Correct 146 ms 9940 KB Output is correct
8 Correct 184 ms 10924 KB Output is correct
9 Correct 890 ms 12292 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 19 ms 8296 KB Output is correct
13 Correct 16 ms 8236 KB Output is correct
14 Correct 21 ms 8220 KB Output is correct
15 Correct 49 ms 9040 KB Output is correct
16 Correct 130 ms 9844 KB Output is correct
17 Correct 182 ms 10884 KB Output is correct
18 Correct 831 ms 12356 KB Output is correct
19 Execution timed out 1566 ms 40688 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 24 ms 8316 KB Output is correct
4 Correct 16 ms 8256 KB Output is correct
5 Correct 24 ms 8268 KB Output is correct
6 Correct 52 ms 9060 KB Output is correct
7 Correct 146 ms 9940 KB Output is correct
8 Correct 184 ms 10924 KB Output is correct
9 Correct 890 ms 12292 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 20 ms 8368 KB Output is correct
13 Correct 14 ms 8276 KB Output is correct
14 Correct 19 ms 8280 KB Output is correct
15 Correct 50 ms 9108 KB Output is correct
16 Correct 144 ms 9820 KB Output is correct
17 Correct 157 ms 10900 KB Output is correct
18 Correct 826 ms 12256 KB Output is correct
19 Correct 130 ms 29212 KB Output is correct
20 Execution timed out 1587 ms 21980 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 31024 KB Output is correct
2 Correct 282 ms 30972 KB Output is correct
3 Correct 331 ms 30824 KB Output is correct
4 Correct 93 ms 21304 KB Output is correct
5 Correct 187 ms 28164 KB Output is correct
6 Execution timed out 1569 ms 40484 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 307 ms 30960 KB Output is correct
3 Correct 284 ms 31000 KB Output is correct
4 Correct 341 ms 30884 KB Output is correct
5 Correct 292 ms 30124 KB Output is correct
6 Correct 292 ms 29228 KB Output is correct
7 Correct 341 ms 29020 KB Output is correct
8 Correct 115 ms 23016 KB Output is correct
9 Correct 90 ms 21468 KB Output is correct
10 Correct 241 ms 28184 KB Output is correct
11 Correct 229 ms 26212 KB Output is correct
12 Correct 89 ms 24436 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 24 ms 8316 KB Output is correct
16 Correct 16 ms 8256 KB Output is correct
17 Correct 24 ms 8268 KB Output is correct
18 Correct 52 ms 9060 KB Output is correct
19 Correct 146 ms 9940 KB Output is correct
20 Correct 184 ms 10924 KB Output is correct
21 Correct 890 ms 12292 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 19 ms 8296 KB Output is correct
25 Correct 16 ms 8236 KB Output is correct
26 Correct 21 ms 8220 KB Output is correct
27 Correct 49 ms 9040 KB Output is correct
28 Correct 130 ms 9844 KB Output is correct
29 Correct 182 ms 10884 KB Output is correct
30 Correct 831 ms 12356 KB Output is correct
31 Execution timed out 1566 ms 40688 KB Time limit exceeded
32 Halted 0 ms 0 KB -