Submission #602361

#	Time	Username	Problem	Language	Result	Execution time	Memory
602361		APROHACK	Highway Tolls (IOI18_highway)	C++14	0 / 100	129 ms	7792 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ff first
#define ss second
using namespace std;
ll m, n, AA, BB, largo, e, subA, subB, largoA, largoB; //n = cities, m = edges
vector<pair<int, int> >adj[90000]; // nodo, indx
vector<int>w;
bool vis[100005];
bool test(int li, int pos, int ls){
  for(int i = 0 ; i < m ; i++)w[i]=0;
  for(int i = li ; i <= pos ; i++)w[i]=1;
  //for(int i = pos+1 ; i < ls ; i++)w[i]=0;
  if(ask(w) == largo*AA )return false;
  else return true;
}
void findE(){
  int li=0, ls=m-1, pos=(m-1)/2;
  while(li<ls){
    pos = (li+ls)/2;
    if(test(li, pos, ls))ls=pos;
    else li=pos+1;
  }
  e = li;
}
void findSize(){
  memset(vis, false, sizeof vis);
  queue<int>nxt;
  nxt.push(subA);
  vis[subA]=true;
  for(int i = 0 ; i < m ; i++)w[i]=0;
  while(!nxt.empty()){
    int cur = nxt.front();
    nxt.pop();
    for(int i = 0 ; i < adj[cur].size() ; i ++){
      if(vis[adj[cur][i].ff] || adj[cur][i].ss == e)continue;
      ////cout<< " ll " << adj[cur][i].ff << endl;
      vis[adj[cur][i].ff]=true;
      w[adj[cur][i].ss]=1;
      nxt.push(adj[cur][i].ff);
    }
  }
  ////cout<< ask(w)<<endl;
  largoA = (ask(w)-largo)/(BB-AA);
  nxt.push(subB);
  for(int i = 0 ; i < m ; i++)w[i]=0;
  memset(vis, false, sizeof vis);
  vis[subB]=true;
  while(!nxt.empty()){
    int cur = nxt.front();
    nxt.pop();
    for(int i = 0 ; i < adj[cur].size() ; i ++){
      if(vis[adj[cur][i].ff] || adj[cur][i].ss == e)continue;
      ////cout<<" ll " << adj[cur][i].ff << endl;
      vis[adj[cur][i].ff]=true;
      w[adj[cur][i].ss]=1;
      nxt.push(adj[cur][i].ff);
    }
  }
  memset(vis, false, sizeof vis);
  ////cout<< ask(w)<<endl;
  largoB = (ask(w)-largo)/(BB-AA);
}
ll  findNode(int start, int dist){
  //cout << "finding " << start << " " << dist<<endl;

  vector<int>posibilidades, nodoahi;
  queue <pair<int, int>  > q;
  memset(vis, false, sizeof vis);
  
  q.push({start, 0}); // nodo, dist
  vis[start]=true;
  while(!q.empty()){
    pair<int , int> cur = q.front();
    q.pop();
    for(int i = 0 ; i < adj[cur.ff].size() ; i++){
      if(vis[adj[cur.ff][i].ff] || adj[cur.ff][i].ss == e)continue;
      if(cur.ss+1 == dist){
        //cout<<"putin" << adj[cur.ff][i].ss << endl;
        posibilidades.pb(adj[cur.ff][i].ss);
        nodoahi.pb(adj[cur.ff][i].ff);
        continue;
      }
      vis[adj[cur.ff][i].ff] = true;
      //cout << "in" << adj[cur.ff][i].ff <<endl;
      q.push({adj[cur.ff][i].ff, cur.ss+1});
    }
  }
  
  if(!posibilidades.size())posibilidades.pb(e), nodoahi.pb(start);
  //cout<< "pp \n";
  //for(int i = 0 ; i < posibilidades.size() ; i ++ ) //cout<<posibilidades[i] << " ";
  //cout << endl; 

  int li = 0, ls = posibilidades.size();
  int pos = (li+ls)/2;
  while(li<ls){
    pos = (li+ls)/2;
    for(int i = 0 ; i < m ; i ++)w[i]=0;
    for(int i = li ; i <= pos ; i++)w[posibilidades[i]]=1;
    if(ask(w)==largo){
      li=pos+1;
    }else{
      ls = pos;
    }
  }
  //cout<< " ans " << nodoahi[li] <<endl;
  return nodoahi[li];
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  m = U.size();
  n = N;
  AA=A;
  BB=B;
  for(int i = 0 ; i < m ; i++){
    adj[U[i]].pb({V[i], i});
    adj[V[i]].pb({U[i], i} );
  }
  
    for (int i = 0; i < m; ++i) {
      w.pb(0);
    }
    largo = ask(w) / A;
    //cout<<"L"<<largo<<endl;
    findE();
    //cout<<e<<endl;
    subA=U[e], subB=V[e];
    findSize();
    //cout<<largoA << " " << largoB << endl;
    answer(findNode(subA, largoA), findNode(subB, largoB));
}

Compilation message (stderr)

highway.cpp: In function 'void findSize()':
highway.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0 ; i < adj[cur].size() ; i ++){
      |                     ~~^~~~~~~~~~~~~~~~~
highway.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 0 ; i < adj[cur].size() ; i ++){
      |                     ~~^~~~~~~~~~~~~~~~~
highway.cpp: In function 'long long int findNode(int, int)':
highway.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 0 ; i < adj[cur.ff].size() ; i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31