Submission #433312

#	Time	Username	Problem	Language	Result	Execution time	Memory
433312		ioi	Highway Tolls (IOI18_highway)	C++14	0 / 100	117 ms	4516 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std ;

const int N = 9e4 + 4 ;

long long ds[N] , vis[N] , vid , par[N];

vector<int> adj[N];


void bfs(int s){

    ds[s] = 0 ;
    vid ++ ;

    queue<int> q ;

    q.push(s);


    while(q.size()){

        auto fr = q.front();
        q.pop();


        for(auto f : adj[fr]){

            if(vid != vis[f]){

                vis[f] = vid ;

                q.push(f);
                par[f] = fr ;

                ds[f] = ds[fr]  + 1 ;


            }

        }

    }

}


void find_pair(int N, std::vector<int> u, std::vector<int> v, int A, int B) {
  int M = u.size() , n = N ;
   // map<pair<int , int > , int > mp ;


//  for(int i = 0 ; i < M ; i ++)
  //  adj[u[i]].push_back(v[i]) , adj[v[i]].push_back(u[i]) , mp[{u[i] , v[i]}] = mp[{v[i] , u[i]}] = i;


  vector<int> w(M , 0);

  long long toll = ask(w);

 // bfs(0);


    int d = toll / A ;


    int l = 0 , r = M - 1 , md ;


    while(l <= r){


        md = (l + r) / 2 ;

        w = vector<int> (M , 0);

        for(int i = l ; i <= md ; i ++)w[i] =1 ;



        long long toll2 = ask(w);
       // cout << "toll2 " << toll2 << endl;

        if(l == r){

            answer(l , r + 1);
            break; 

        }
        if(toll == toll2)l = md + 1 ;
        else if(toll2 == d * B)r = md ;
        else {

            // Bx + Ay  = toll2
            // x + y = d

            //3x + 1y = 5
            //x + y = 3

            long long v = toll2 - B * d ;

            long long v2 = A - B ;
            v /= v2 ;
            //cout << "V " << v << endl;
            int rest = d - v ;
            answer(md + 1 - rest , md + 1 + v);
            break;

        }



    }



 // vector<int> poss ;

 // for(int i = 1 ; i < n ; i ++)
   // if(ds[i] == toll / A)poss.push_back(i);



   // int l = 0 , r = poss.size() - 1 , md ;

 //   while(l < r){

    //    md = (l + r ) / 2 ;


     //   w = vector<int> (M , 0);
/*
        for(int i = l ; i <= md ; i ++)
            w[mp[{par[poss[i]] , poss[i]}]] = 1 ;

        long long toll2 = ask(w);

        if(toll == toll2)
            l = md + 1 ;
        else r = md ;

       // cout << l << " " << md << " " << r << endl;

    //}



  answer(0, poss[l]);*/
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:50:22: warning: unused variable 'n' [-Wunused-variable]
   50 |   int M = u.size() , n = N ;
      |                      ^

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