oj.uz

답안 #1111711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1111711 2024-11-12T17:38:08 Z noyancanturk Prize (CEOI22_prize) C++17
0 / 100
 1786 ms 390104 KB 
#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]){
    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]){
    par1[j]=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(!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(!ispar2(lift2[x][i],y))x=lift2[x][i];
  }
  return lift2[x][0];
}

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];
  }
  for(int i=1;i<=23;i++){
    for(int j=1;j<=n;j++){
      lift1[j][i]=lift1[lift1[j][i-1]][i-1];
      lift2[j][i]=lift2[lift2[j][i-1]][i-1];
    }
  }
  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

Main.cpp: In function 'void cdfs(int)':
Main.cpp:28:18: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   if(dudes.size()==k)return;
      |      ~~~~~~~~~~~~^~~
Main.cpp:30:18: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |   if(dudes.size()==k)return;
      |      ~~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:106:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i=0;i+1<order.size();i++){
      |               ~~~^~~~~~~~~~~~~
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:90:7: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |   cdfs(root1);
      |   ~~~~^~~~~~~
Main.cpp:95:7: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |   odfs(root2);
      |   ~~~~^~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 962 ms 219836 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1036 ms 222540 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 784 ms 220272 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1747 ms 379604 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1786 ms 390104 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -