Submission #1111755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111755		noyancanturk	Prize (CEOI22_prize)	C++17	100 / 100	2599 ms	632668 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
using pii=pair<int,int>;

const int lim=1e6+100;

int n,k,q,t;
vector<int>v[lim],u[lim];

int lift1[lim][25],lift2[lim][25];
int tin1[lim],tin2[lim],tout1[lim],tout2[lim];
int dep1[lim],dep2[lim];

int tt=1;

unordered_set<int>dudes;
void edfs(int node){
  for(int i=1;i<=23;i++)
    lift1[node][i]=lift1[lift1[node][i-1]][i-1];
  tin1[node]=tt++;
  if(dudes.size()<k)dudes.insert(node);
  for(int j:v[node]){
    lift1[j][0]=node;
    edfs(j);
  }
  tout1[node]=tt-1;
}

vector<int>order;
void odfs(int node){
  for(int i=1;i<=23;i++)
    lift2[node][i]=lift2[lift2[node][i-1]][i-1];
  tin2[node]=tt++;
  if(dudes.count(node)){
    order.pb(node);
  }
  for(int j:u[node]){
    lift2[j][0]=node;
    odfs(j);
  }
  tout2[node]=tt-1;
}

#define ispar1(x,y) (tin1[x]<=tin1[y]&&tout1[y]<=tout1[x])
#define ispar2(x,y) (tin2[x]<=tin2[y]&&tout2[y]<=tout2[x])

int lca1(int x,int y){
  if(ispar1(x,y))return x;
  if(ispar1(y,x))return y;
  for(int i=23;0<=i;i--){
    if(lift1[x][i]&&!ispar1(lift1[x][i],y))x=lift1[x][i];
  }
  assert(ispar1(lift1[x][0],y)&&!ispar1(x,y));
  return lift1[x][0];
}
int lca2(int x,int y){
  if(ispar2(x,y))return x;
  if(ispar2(y,x))return y;
  for(int i=23;0<=i;i--){
    if(lift2[x][i]&&!ispar2(lift2[x][i],y))x=lift2[x][i];
  }
  assert(ispar2(lift2[x][0],y)&&!ispar2(x,y));
  return lift2[x][0];
}

signed main(){    
  ios::sync_with_stdio(0);cin.tie(0);cout.tie();
  cin>>n>>k>>q>>t;
  int root1,root2;
  for(int i=1;i<=n;i++){
    cin>>lift1[i][0];
    if(lift1[i][0]==-1)root1=i,lift1[i][0]++;
    else v[lift1[i][0]].pb(i);
  }
  for(int i=1;i<=n;i++){
    cin>>lift2[i][0];
    if(lift2[i][0]==-1)root2=i,lift2[i][0]++;
    else u[lift2[i][0]].pb(i);
  }
  tt=1;
  edfs(root1);
  odfs(root2);
  for(int i=0;i<k;i++){
    cout<<order[i];
    if(i==k-1)cout<<endl;
    else cout<<' ';
  }cout.flush();
  for(int i=0;i+1<k;i++){
    cout<<"? "<<order[i]<<' '<<order[i+1]<<endl;
  }
  cout<<"!"<<endl;
  dep1[order[0]]=dep2[order[0]]=0;
  for(int i=0;i+1<k;i++){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int l1=lca1(order[i],order[i+1]);
    int l2=lca2(order[i],order[i+1]);
    dep1[l1]=dep1[order[i]]-a;
    dep2[l2]=dep2[order[i]]-c;
    dep1[order[i+1]]=dep1[l1]+b;
    dep2[order[i+1]]=dep2[l2]+d;
  }
  pii qq[t];
  for(int i=0;i<t;i++)cin>>qq[i].first>>qq[i].second;
  for(auto[x,y]:qq){
    int l1=lca1(x,y);
    int l2=lca2(x,y);
    cout<<dep1[x]+dep1[y]-2*dep1[l1]<<' '<<dep2[x]+dep2[y]-2*dep2[l2]<<endl;
    cout.flush();
  }
}

Compilation message (stderr)

Main.cpp: In function 'void edfs(long long int)':
Main.cpp:23:18: warning: comparison of integer expressions of different signedness: 'std::unordered_set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   23 |   if(dudes.size()<k)dudes.insert(node);
      |      ~~~~~~~~~~~~^~
Main.cpp: In function 'int main()':
Main.cpp:83:7: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |   edfs(root1);
      |   ~~~~^~~~~~~
Main.cpp:84:7: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |   odfs(root2);
      |   ~~~~^~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24