Submission #745558

#	Time	Username	Problem	Language	Result	Execution time	Memory
745558		almothana05	Highway Tolls (IOI18_highway)	C++14	Compilation error	0 ms	0 KiB

highway

#include "highway.h"
#include <bits\stdc++.h>
using namespace std;
vector<pair<long long , long long> >kinder[300000] , ka;
vector<long long>cent , ed;
long long sub[300000], vis[300000];
long long a , b , menge , cmp , comp ,numm , nummer , kind;
long long st , en , mid , mit;
long long centroid(long long x , long long f , long long n){
  for(long long i = 0 ; i < kinder[x].size() ; i++){
    kind = kinder[x][i].first;
    if(vis[kind] != 2 &&kind != f && sub[kind] * 2 > n){
      return centroid(kind , x , n);
    }
  }
  for(long long i = 0 ; i < kinder[x].size() ; i++){
    ed[kinder[x][i].second] = 1;
  }
  vis[x] = 2;
  return x;
}
long long dfs(long long x){
  vis[x] = 1;
  sub[x] = 1;
  for(long long i = 0 ; i < kinder[x].size() ; i++){
    kind = kinder[x][i].first;
    if(vis[kind] == 0){
      sub[x] += dfs(kind);
    }
  }
  return sub[x];
}
long long bis(long long x , long long y , long long z ,long long f , long long root){
    for(long long i = 0 ; i <= y ; i++){
      ed[kinder[root][i].second] = 1;
    }
    st = x ; en = y; mid = y;
    while(st <= en){
      mit = (st + en)/2;
      
        while(mid > mit){
          if(kinder[root][mid].first == f){
            mid--;
            continue;
          }
          ed[kinder[root][mid].second] = 0;
          mid--;
        }
        
        while(mid <= mit){
          if(kinder[root][mid].first == f){
            mid++;
            continue;
          }
          ed[kinder[root][mid].second] = 1;
          mid++;
        }
        if(mid > mit){
          mid--;
        }
        
      numm = ask(ed);
      if(numm >= z){
        en = mit - 1;
      }
      else{
        st = mit + 1;
      }
    }
    return st;
}
long long suche(long long x){
  dfs(x);
  numm = centroid(x ,x , sub[x]);
  // cout << x << ' '<<numm << "\n";
  long long fater,pl;
  for(long long i = 0 ; i < kinder[numm].size() ; i++ ){
    if(sub[kinder[numm][i].first] > sub[numm]){
      fater = kinder[numm][i].first;
      break;
    }
  }
  cmp = ask(ed);
  if(numm == x){
    if(cmp == comp){
      return numm;
    }
    else{
      comp = cmp;
      pl = bis(0 , kinder[numm].size() - 1 , cmp , fater , numm );
    }
  }
  else{
    if(cmp == comp){
      return suche(x);
    }
    else if(cmp == comp + b - a){
      return numm;
    }
    else{
      comp = cmp;
      pl = bis(0 , kinder[numm].size() - 1 , cmp , fater , numm );
    }
  }
  return suche(kinder[numm][pl].first);
}

void finde(){
  for(long long i = 0 ; i < menge ; i++){
    if(vis[i] == 0){
      ka.push_back({i , dfs(i)});
    }
  }
  
  for(long long i = 0 ; i < ka.size() ; i++){
    cent.push_back(centroid(ka[i].first , ka[i].first , ka[i].second));
  }
  for(long long i = 0 ; i < menge ; i++){
    if(vis[i] == 1){
      vis[i] = 0;
    }
  }
  ka.clear();
  comp = ask(ed);
  if(comp > cmp){
    st = 0 ; en = cent.size() - 2; mid = cent.size() - 1;
    while(st <= en){
      mit = (st + en)/2;
      
        while(mid > mit){
          for(long long i = 0 ; i < kinder[cent[mid]].size() ; i++){
            ed[kinder[cent[mid]][i].second] = 0;
          }
          mid--;
        }
        

        while(mid <= mit){
          for(long long i = 0 ; i < kinder[cent[mid]].size() ; i++){
            ed[kinder[cent[mid]][i].second] = 1;
          }
          mid++;
        }
        if(mid > mit){
          mid--;
        }
        
      numm = ask(ed);
      if(numm == comp){
        en = mit - 1;
      }
      else{
        st = mit + 1;
      }
    }
    long long root , er  ,zw;
    root = cent[st];
    cent.clear();
    er = bis(0 , kinder[root].size() - 1 , cmp +b -a , -1 , root);
    // cout << er << "\n";
    if(comp == cmp + b - a){
      zw = root;
      for(long long i = 0 ; i < kinder[root].size() ; i++){
        ed[kinder[root][i].second] = 1;
      }
    }
    else{
      zw = bis(er , kinder[root].size() - 1 , comp , -1 , root);
      // cout << zw << "\n";
      for(long long i = 0 ; i < kinder[root].size() ; i++){
        ed[kinder[root][i].second] = 1;
      } 
      // cout << kinder[root][er].first << "\n";
      zw = suche(kinder[root][zw].first);
    }
    er = suche(kinder[root][er].first);
    answer(er , zw);
    return;
  }
  cent.clear();
  finde();
}
void find_pair(long long N, vector<long long> u, vector<long long> v, long long A, long long B) {
  a = A;
  b = B;
  menge = N;

  for(long long i = 0 ; i < u.size() ; i++){
    kinder[u[i]].push_back({v[i] , i});
    kinder[v[i]].push_back({u[i] , i});
    ed.push_back(0);
  }
  cmp = ask(ed);
  finde();
}

Compilation message (stderr)

highway.cpp:2:10: fatal error: bits\stdc++.h: No such file or directory
    2 | #include <bits\stdc++.h>
      |          ^~~~~~~~~~~~~~~
compilation terminated.