oj.uz

답안 #603825

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603825 2022-07-24T12:09:01 Z DanerZein Event Hopping (BOI22_events) C++14
20 / 100
 1500 ms 42048 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;
  deque<int> q; q.push_back(u);
  while(!q.empty()){
    int x=q.front(); q.pop_front();
    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;
	  if(!q.empty() && dis[q.front()]>dis[v])
	    q.push_front(v);
	  else q.push_back(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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 235 ms 28056 KB Output is correct
3 Correct 237 ms 28048 KB Output is correct
4 Correct 263 ms 28036 KB Output is correct
5 Correct 249 ms 27008 KB Output is correct
6 Correct 236 ms 26192 KB Output is correct
7 Correct 262 ms 25924 KB Output is correct
8 Correct 108 ms 19884 KB Output is correct
9 Correct 86 ms 18484 KB Output is correct
10 Correct 173 ms 25056 KB Output is correct
11 Correct 165 ms 23252 KB Output is correct
12 Correct 78 ms 22132 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 19 ms 8276 KB Output is correct
4 Correct 13 ms 8276 KB Output is correct
5 Correct 20 ms 8296 KB Output is correct
6 Correct 48 ms 9020 KB Output is correct
7 Correct 133 ms 9948 KB Output is correct
8 Correct 139 ms 10952 KB Output is correct
9 Correct 711 ms 12484 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 19 ms 8276 KB Output is correct
4 Correct 13 ms 8276 KB Output is correct
5 Correct 20 ms 8296 KB Output is correct
6 Correct 48 ms 9020 KB Output is correct
7 Correct 133 ms 9948 KB Output is correct
8 Correct 139 ms 10952 KB Output is correct
9 Correct 711 ms 12484 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 8276 KB Output is correct
13 Correct 13 ms 8348 KB Output is correct
14 Correct 19 ms 8252 KB Output is correct
15 Correct 56 ms 8996 KB Output is correct
16 Correct 122 ms 9876 KB Output is correct
17 Correct 144 ms 10972 KB Output is correct
18 Correct 729 ms 12248 KB Output is correct
19 Execution timed out 1591 ms 42048 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 19 ms 8276 KB Output is correct
4 Correct 13 ms 8276 KB Output is correct
5 Correct 20 ms 8296 KB Output is correct
6 Correct 48 ms 9020 KB Output is correct
7 Correct 133 ms 9948 KB Output is correct
8 Correct 139 ms 10952 KB Output is correct
9 Correct 711 ms 12484 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 19 ms 8320 KB Output is correct
13 Correct 13 ms 8332 KB Output is correct
14 Correct 19 ms 8300 KB Output is correct
15 Correct 48 ms 9008 KB Output is correct
16 Correct 133 ms 9840 KB Output is correct
17 Correct 139 ms 10888 KB Output is correct
18 Correct 775 ms 12332 KB Output is correct
19 Correct 106 ms 27332 KB Output is correct
20 Execution timed out 1586 ms 21068 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 27900 KB Output is correct
2 Correct 242 ms 27944 KB Output is correct
3 Correct 268 ms 27920 KB Output is correct
4 Correct 84 ms 18440 KB Output is correct
5 Correct 186 ms 25144 KB Output is correct
6 Execution timed out 1591 ms 38532 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 235 ms 28056 KB Output is correct
3 Correct 237 ms 28048 KB Output is correct
4 Correct 263 ms 28036 KB Output is correct
5 Correct 249 ms 27008 KB Output is correct
6 Correct 236 ms 26192 KB Output is correct
7 Correct 262 ms 25924 KB Output is correct
8 Correct 108 ms 19884 KB Output is correct
9 Correct 86 ms 18484 KB Output is correct
10 Correct 173 ms 25056 KB Output is correct
11 Correct 165 ms 23252 KB Output is correct
12 Correct 78 ms 22132 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 19 ms 8276 KB Output is correct
16 Correct 13 ms 8276 KB Output is correct
17 Correct 20 ms 8296 KB Output is correct
18 Correct 48 ms 9020 KB Output is correct
19 Correct 133 ms 9948 KB Output is correct
20 Correct 139 ms 10952 KB Output is correct
21 Correct 711 ms 12484 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 8276 KB Output is correct
25 Correct 13 ms 8348 KB Output is correct
26 Correct 19 ms 8252 KB Output is correct
27 Correct 56 ms 8996 KB Output is correct
28 Correct 122 ms 9876 KB Output is correct
29 Correct 144 ms 10972 KB Output is correct
30 Correct 729 ms 12248 KB Output is correct
31 Execution timed out 1591 ms 42048 KB Time limit exceeded
32 Halted 0 ms 0 KB -