oj.uz

Submission #1105504

# Submission time Handle Problem Language Result Execution time Memory
1105504 2024-10-26T14:55:38 Z epicci23 Prize (CEOI22_prize) C++17
0 / 100
 672 ms 120064 KB 
#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 5e5 + 5;
const int LOG = 20;
int n,q,k,t;
 vector<int> sec;
vector<int> v[N],g[N];
int depth[N],up[N][LOG],in[N],out[N],R;
int par[N],r,tin[N],tout[N],lift[N][LOG],ti=0;

void dfs(int c){
   tin[c]=++ti;
   for(int i=1;i<LOG;i++) lift[c][i]=lift[lift[c][i-1]][i-1];
   for(int x:v[c]){
   	 if(x==par[c]) continue;
   	 dfs(x);
   }
   tout[c]=ti;
}

void dfs2(int c){
  in[c]=++ti;
  for(int i=1;i<LOG;i++) up[c][i]=up[up[c][i-1]][i-1];
  for(int x:g[c]) dfs2(x);
  out[c]=ti;
}


inline bool is_anc(int a,int b){
  return tin[a]<=tin[b] && tout[b]<=tout[a]; 
}

inline int lca(int a,int b){
  if(tin[a]>=tin[b]) swap(a,b);
  if(is_anc(a,b)) return a;
  for(int i=LOG-1;i>=0;i--){
  	if(!lift[a][i]) continue;
  	if(!is_anc(lift[a][i],b)) a=lift[a][i];
  }
  return lift[a][0];
}

inline bool Vis_anc(int a,int b){
  return in[a]<=in[b] && out[b]<=out[a]; 
}

inline int Vlca(int a,int b){
  if(in[a]>=in[b]) swap(a,b);
  if(Vis_anc(a,b)) return a;
  for(int i=LOG-1;i>=0;i--){
  	if(!up[a][i]) continue;
  	if(!Vis_anc(up[a][i],b)) a=up[a][i];
  }
  return up[a][0];
}

inline int dist(int a,int b){
  return depth[a]+depth[b]-2*depth[Vlca(a,b)];
}

inline array<int,2> Answer(int a,int b){
  return {dist(a,b),dist(a,b)};
}

void kac(int c){
  if(sz(sec)==k) return;
  sec.push_back(c);
  if(sz(sec)==k) return;
  for(int x:v[c]) kac(x);
}


void _(){
  cin >> n >> k >> q >> t;
  for(int i=1;i<=n;i++) cin >> par[i];
  for(int i=1;i<=n;i++) cin >> par[i];

  for(int i=1;i<=n;i++){
    if(par[i]==-1) r=i;
    else{
      lift[i][0]=par[i];
      v[par[i]].push_back(i);
      v[i].push_back(par[i]);
    }
  }
  
  ti=0;
  dfs(r);
  kac(r);
  vector<array<int,2>> ask;
  vector<int> virt;
  for(int i:sec) virt.push_back(i);

  sort(all(virt),[&](int a,int b){return tin[a]<tin[b];});
  for(int i=1;i<k;i++) virt.push_back(lca(virt[i-1],virt[i]));
  sort(all(virt),[&](int a,int b){return tin[a]<tin[b];});
  virt.erase(unique(all(virt)),virt.end());
  R=virt[0];
  stack<int> s;

	  for(int x:virt){
	    while(!s.empty() && !is_anc(s.top(),x)) s.pop();
	    if(!s.empty()){
	    	ask.push_back({s.top(),x});
	    	up[x][0]=s.top();
	    	g[s.top()].push_back(x);
	    }
	    s.push(x);
	  }
	  ti=0;
	  dfs2(R);

 for(int x:sec) cout << x << ' ';
 cout << endl;
 for(auto x:ask) cout << "? " << x[0] << ' ' << x[1] << endl;
 cout << '!' << endl;

 for(int i=0;i<sz(ask);i++){
   int a = ask[i][0] , b = ask[i][1];
   int res[4];
   cin >> res[0] >> res[1] >> res[2] >> res[3];
   depth[b]=depth[a]+res[1];
 }

 vector<array<int,2>> U;
 for(int i=1;i<=t;i++){
 	int a,b;
 	cin >> a >> b;
 	U.push_back({a,b});
 }

 for(auto S:U){
   int a = S[0] , b = S[1];
   auto ANS = Answer(a,b);
   cout << ANS[0] << ' ' << ANS[1] << endl;
 }

}

int32_t main(){
  //cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 477 ms 120064 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 516 ms 118728 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 672 ms 116896 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 451 ms 63680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 422 ms 63676 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -