oj.uz

Submission #1111755

# Submission time Handle Problem Language Result Execution time Memory
1111755 2024-11-12T18:53:54 Z noyancanturk Prize (CEOI22_prize) C++17
100 / 100
 2599 ms 632668 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 946 ms 357040 KB Output is correct
2 Correct 1061 ms 359200 KB Output is correct
3 Correct 875 ms 306276 KB Output is correct
4 Correct 809 ms 304100 KB Output is correct
5 Correct 822 ms 296228 KB Output is correct
6 Correct 1149 ms 303052 KB Output is correct
7 Correct 1055 ms 304504 KB Output is correct
8 Correct 1188 ms 302968 KB Output is correct
9 Correct 931 ms 294412 KB Output is correct
10 Correct 967 ms 297160 KB Output is correct
11 Correct 870 ms 293816 KB Output is correct
12 Correct 841 ms 294216 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1142 ms 347536 KB Output is correct
2 Correct 1031 ms 343740 KB Output is correct
3 Correct 864 ms 298708 KB Output is correct
4 Correct 928 ms 296372 KB Output is correct
5 Correct 872 ms 294464 KB Output is correct
6 Correct 1123 ms 304224 KB Output is correct
7 Correct 1274 ms 315688 KB Output is correct
8 Correct 1213 ms 315688 KB Output is correct
9 Correct 1254 ms 308496 KB Output is correct
10 Correct 1032 ms 306640 KB Output is correct
11 Correct 1103 ms 305200 KB Output is correct
12 Correct 1130 ms 307932 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 341940 KB Output is correct
2 Correct 860 ms 339988 KB Output is correct
3 Correct 621 ms 290236 KB Output is correct
4 Correct 629 ms 286900 KB Output is correct
5 Correct 520 ms 289452 KB Output is correct
6 Correct 671 ms 294836 KB Output is correct
7 Correct 712 ms 294900 KB Output is correct
8 Correct 792 ms 297652 KB Output is correct
9 Correct 786 ms 297636 KB Output is correct
10 Correct 742 ms 288436 KB Output is correct
11 Correct 725 ms 288584 KB Output is correct
12 Correct 702 ms 294068 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2074 ms 620252 KB Output is correct
2 Correct 2114 ms 617516 KB Output is correct
3 Correct 1568 ms 516800 KB Output is correct
4 Correct 1541 ms 516744 KB Output is correct
5 Correct 1558 ms 516532 KB Output is correct
6 Correct 2033 ms 535076 KB Output is correct
7 Correct 2139 ms 535504 KB Output is correct
8 Correct 2040 ms 535212 KB Output is correct
9 Correct 1885 ms 529024 KB Output is correct
10 Correct 1906 ms 529132 KB Output is correct
11 Correct 1829 ms 526540 KB Output is correct
12 Correct 1936 ms 529088 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2401 ms 632664 KB Output is correct
2 Correct 2363 ms 632668 KB Output is correct
3 Correct 1756 ms 528364 KB Output is correct
4 Correct 1810 ms 530904 KB Output is correct
5 Correct 1768 ms 528376 KB Output is correct
6 Correct 2599 ms 549164 KB Output is correct
7 Correct 2583 ms 546488 KB Output is correct
8 Correct 2381 ms 547412 KB Output is correct
9 Correct 2197 ms 538768 KB Output is correct
10 Correct 2180 ms 538204 KB Output is correct
11 Correct 2025 ms 538216 KB Output is correct
12 Correct 2257 ms 539472 KB Output is correct