Submission #1111722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111722		noyancanturk	Prize (CEOI22_prize)	C++17	0 / 100	2928 ms	389092 KiB

Main

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

const int lim=1e6+100;

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

int par1[lim],par2[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;

void edfs(int node){
  tin1[node]=tt++;
  for(int j:v[node]){
    par1[j]=node;
    edfs(j);
  }
  tout1[node]=tt-1;
}

unordered_set<int>dudes;
void cdfs(int node){
  if(dudes.size()==k)return;
  dudes.insert(node);
  if(dudes.size()==k)return;
  for(int j:v[node]){
    cdfs(j);
  }
}

vector<int>order;
void odfs(int node){
  tin2[node]=tt++;
  if(dudes.count(node)){
    order.pb(node);
  }
  for(int j:u[node]){
    par2[j]=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];
  }
  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];
  }
  return lift2[x][0];
}

void ldfs1(int node){
  for(int i=1;i<=23;i++)
    lift1[node][i]=lift1[lift1[node][i-1]][i-1];
  for(int j:v[node])ldfs1(j);
}

void ldfs2(int node){
  for(int i=1;i<=23;i++)
    lift2[node][i]=lift2[lift2[node][i-1]][i-1];
  for(int j:u[node])ldfs2(j);
}

int main(){
  cin>>n>>k>>q>>t;
  int root1,root2;
  for(int i=1;i<=n;i++){
    int p;
    cin>>p;
    if(p==-1)root1=i;
    else v[p].pb(i);
  }
  for(int i=1;i<=n;i++){
    int p;
    cin>>p;
    if(p==-1)root2=i;
    else u[p].pb(i);
  }
  tin1[0]=tin2[0]=INT_MIN;
  tout1[0]=tout2[0]=INT_MAX;
  tt=1;
  edfs(root1);
  cdfs(root1);
  for(int i:dudes)cout<<i<<' ';
  cout<<endl;
  cout.flush();
  tt=1;
  odfs(root2);
  for(int i=1;i<=n;i++){
    lift1[i][0]=par1[i];
    lift2[i][0]=par2[i];
  }
  ldfs1(root1);
  ldfs2(root2);
  for(int i=0;i+1<order.size();i++){
    cout<<"? "<<order[i]<<' '<<order[i+1]<<endl;
  }
  cout<<"!";
  cout<<endl;
  cout.flush();
  dep1[order[0]]=dep2[order[0]]=0;
  for(int i=0;i+1<order.size();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;
  }
  for(int i=0;i<t;i++){
    int x,y;
    cin>>x>>y;
    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 cdfs(int)':
Main.cpp:29:18: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |   if(dudes.size()==k)return;
      |      ~~~~~~~~~~~~^~~
Main.cpp:31:18: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |   if(dudes.size()==k)return;
      |      ~~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i=0;i+1<order.size();i++){
      |               ~~~^~~~~~~~~~~~~
Main.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for(int i=0;i+1<order.size();i++){
      |               ~~~^~~~~~~~~~~~~
Main.cpp:111:8: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |   ldfs1(root1);
      |   ~~~~~^~~~~~~
Main.cpp:112:8: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |   ldfs2(root2);
      |   ~~~~~^~~~~~~

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