Submission #433295

#	Time	Username	Problem	Language	Result	Execution time	Memory
433295		ioi	Highway Tolls (IOI18_highway)	C++14	12 / 100	377 ms	21204 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);

  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:65:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   65 |   for(int i = 1 ; i < n ; i ++)
      |   ^~~
highway.cpp:70:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   70 |     int l = 0 , r = poss.size() - 1 , md ;
      |     ^~~

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