oj.uz

Submission #603307

# Submission time Handle Problem Language Result Execution time Memory
603307 2022-07-24T00:08:42 Z DanerZein Event Hopping (BOI22_events) C++14
20 / 100
 1500 ms 40380 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;
vector<vii> que;
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);
      }
    }
  }
  int iq=0;
  que.resize(n);
  while(q--){
    int s,e; cin>>s>>e;
    s--; e--;
    if(t2){
      que[s].push_back(ii(e,iq));
      iq++;
    }
    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";
      }
    }
  }
  if(t2){
    vector<int> ans(iq);
    for(int i=0;i<n;i++){
      bfs(i);
      for(auto &v:que[i]){
	int s=i; int e=v.first;
	bfs(s);
	if(dis[e]>=MAX) ans[v.second]=-1;
	else ans[v.second]=dis[e];
      }
    }
    for(int i=0;i<ans.size();i++){
      if(ans[i]==-1) cout<<"impossible\n";
      else cout<<ans[i]<<endl;
    }
  }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:139:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for(int i=0;i<ans.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 243 ms 33028 KB Output is correct
3 Correct 237 ms 32944 KB Output is correct
4 Correct 279 ms 32928 KB Output is correct
5 Correct 238 ms 31192 KB Output is correct
6 Correct 233 ms 30312 KB Output is correct
7 Correct 301 ms 30068 KB Output is correct
8 Correct 117 ms 24040 KB Output is correct
9 Correct 93 ms 22444 KB Output is correct
10 Correct 207 ms 29388 KB Output is correct
11 Correct 167 ms 27360 KB Output is correct
12 Correct 78 ms 25880 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 1 ms 212 KB Output is correct
3 Correct 19 ms 428 KB Output is correct
4 Correct 12 ms 368 KB Output is correct
5 Correct 17 ms 340 KB Output is correct
6 Correct 40 ms 1216 KB Output is correct
7 Correct 118 ms 2036 KB Output is correct
8 Correct 142 ms 3088 KB Output is correct
9 Correct 696 ms 4500 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 1 ms 212 KB Output is correct
3 Correct 19 ms 428 KB Output is correct
4 Correct 12 ms 368 KB Output is correct
5 Correct 17 ms 340 KB Output is correct
6 Correct 40 ms 1216 KB Output is correct
7 Correct 118 ms 2036 KB Output is correct
8 Correct 142 ms 3088 KB Output is correct
9 Correct 696 ms 4500 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 21 ms 428 KB Output is correct
13 Correct 11 ms 468 KB Output is correct
14 Correct 19 ms 340 KB Output is correct
15 Correct 43 ms 1236 KB Output is correct
16 Correct 116 ms 2036 KB Output is correct
17 Correct 148 ms 3092 KB Output is correct
18 Correct 749 ms 4428 KB Output is correct
19 Execution timed out 1556 ms 31068 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 1 ms 212 KB Output is correct
3 Correct 19 ms 428 KB Output is correct
4 Correct 12 ms 368 KB Output is correct
5 Correct 17 ms 340 KB Output is correct
6 Correct 40 ms 1216 KB Output is correct
7 Correct 118 ms 2036 KB Output is correct
8 Correct 142 ms 3088 KB Output is correct
9 Correct 696 ms 4500 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 19 ms 408 KB Output is correct
13 Correct 12 ms 456 KB Output is correct
14 Correct 17 ms 444 KB Output is correct
15 Correct 45 ms 1220 KB Output is correct
16 Correct 125 ms 2036 KB Output is correct
17 Correct 136 ms 3092 KB Output is correct
18 Correct 697 ms 4436 KB Output is correct
19 Correct 110 ms 31292 KB Output is correct
20 Execution timed out 1575 ms 22264 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 33256 KB Output is correct
2 Correct 242 ms 33332 KB Output is correct
3 Correct 290 ms 33056 KB Output is correct
4 Correct 93 ms 23684 KB Output is correct
5 Correct 207 ms 30504 KB Output is correct
6 Execution timed out 1579 ms 40380 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 243 ms 33028 KB Output is correct
3 Correct 237 ms 32944 KB Output is correct
4 Correct 279 ms 32928 KB Output is correct
5 Correct 238 ms 31192 KB Output is correct
6 Correct 233 ms 30312 KB Output is correct
7 Correct 301 ms 30068 KB Output is correct
8 Correct 117 ms 24040 KB Output is correct
9 Correct 93 ms 22444 KB Output is correct
10 Correct 207 ms 29388 KB Output is correct
11 Correct 167 ms 27360 KB Output is correct
12 Correct 78 ms 25880 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 19 ms 428 KB Output is correct
16 Correct 12 ms 368 KB Output is correct
17 Correct 17 ms 340 KB Output is correct
18 Correct 40 ms 1216 KB Output is correct
19 Correct 118 ms 2036 KB Output is correct
20 Correct 142 ms 3088 KB Output is correct
21 Correct 696 ms 4500 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 21 ms 428 KB Output is correct
25 Correct 11 ms 468 KB Output is correct
26 Correct 19 ms 340 KB Output is correct
27 Correct 43 ms 1236 KB Output is correct
28 Correct 116 ms 2036 KB Output is correct
29 Correct 148 ms 3092 KB Output is correct
30 Correct 749 ms 4428 KB Output is correct
31 Execution timed out 1556 ms 31068 KB Time limit exceeded
32 Halted 0 ms 0 KB -