oj.uz

Submission #1105501

# Submission time Handle Problem Language Result Execution time Memory
1105501 2024-10-26T14:44:01 Z epicci23 Prize (CEOI22_prize) C++17
0 / 100
 1743 ms 524260 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> v[N][2],g[N][2];
int depth[N][2],up[N][LOG][2],in[N][2],out[N][2],R[2];
int par[N][2],r[2],tin[N][2],tout[N][2],lift[N][LOG][2],ti=0;

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

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


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

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

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

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

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

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


void _(){
  cin >> n >> k >> q >> t;
  for(int i=1;i<=n;i++) cin >> par[i][0];
  for(int i=1;i<=n;i++) cin >> par[i][1];
  for(int i=1;i<=n;i++){
    if(par[i][0]==-1) r[0]=i;
    else{
      lift[i][0][0]=par[i][0];
      v[par[i][0]][0].push_back(i);
      v[i][0].push_back(par[i][0]);
    }
  }
  for(int i=1;i<=n;i++){
    if(par[i][1]==-1) r[1]=i;
    else{
      lift[i][0][1]=par[i][1];
      v[par[i][1]][1].push_back(i);
      v[i][1].push_back(par[i][1]);
    }
  }

  for(int u=0;u<2;u++){
  	ti=0;
  	dfs(r[u],u);
  }

  vector<int> sec;
  vector<array<int,3>> ask;
  for(int i=1;i<=k;i++) sec.push_back(i);
  
  for(int u=0;u<2;u++){
	  vector<int> virt;
	  for(int i=1;i<=k;i++) virt.push_back(i);

	  sort(all(virt),[&](int a,int b){
	    return tin[a][u]<tin[b][u];
	  });

	  for(int i=1;i<k;i++) virt.push_back(lca(virt[i-1],virt[i],u));
	  
	  sort(all(virt),[&](int a,int b){
	    return tin[a][u]<tin[b][u];
	  });

	  virt.erase(unique(all(virt)),virt.end());
	  R[u]=virt[0];
	  stack<int> s;

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

 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] , u = ask[i][2];
   int res[4];
   cin >> res[0] >> res[1] >> res[2] >> res[3];
   if(u==0) depth[b][u]=depth[a][u]+res[1];
   else depth[b][u]=depth[a][u]+res[3];
 }

 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 Correct 1424 ms 226852 KB Output is correct
2 Correct 1441 ms 237492 KB Output is correct
3 Runtime error 923 ms 264500 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1743 ms 237052 KB Output is correct
2 Correct 1477 ms 221152 KB Output is correct
3 Runtime error 818 ms 264384 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1142 ms 206572 KB Output is correct
2 Correct 1186 ms 206724 KB Output is correct
3 Runtime error 1181 ms 524260 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 613 ms 119132 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 522 ms 119152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -