Submission #433453

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
433453	2021-06-19T20:23:50 Z	ioi	Highway Tolls (IOI18_highway)	C++14	13 / 100	1370 ms	262148 KB

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];

int U , V ;
map<pair<int , int > , int > mp ;

vector<int> w ;
void bfs(int s){
    memset(ds , 0 , sizeof ds);

    ds[s] = 0 ;
    vid ++ ;

    queue<int> q ;

    q.push(s);

    vis[s] = vid ;
    while(q.size()){

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


        for(auto f : adj[fr]){
            if(w[mp[{fr , f}]])continue ;

            if(vid != vis[f]){

                vis[f] = vid ;

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

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


            }

        }

    }

}

void dfs(int u , int p , int number){


    for(auto f : adj[u]){

        if(f != p){
            w[mp[{u , f}]] = number ;

            dfs(f , u , number);
        }

    }



}

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



  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;


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



  long long toll = ask(w) , d = toll / A;


  vector<int> edges;

  for(int i = 0 ; i < M ; i ++)
    edges.push_back(i);

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

  while(l < r){


    md = (l + r) / 2 ;
    //cout << l << " " << md << " " << r << endl ;

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


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

    long long toll2 = ask(edges);
  //  cout << "DD" << toll << " " << toll2 << endl;
    if(toll == toll2)l = md + 1 ;
    else r = md ;



  }

  U = u[l] , V = v[l];
    w = vector<int> (M , 0);


    dfs(U , V , 1);

    long long toll2 = ask(w);

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

    long long va = B - A ;
    long long v2 = B * d - toll2 ;

    v2 /= va ;
    int rest = d - v2 ;

  bfs(V);


    toll = toll2;
    vector<int> poss ;

    for(int i = 0 ; i < n; i ++){
        if(i != U && ds[i] == v2 - 1 )poss.push_back(i);
    }


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

    while(l < r){

        md = (l + r ) / 2 ;

//cout << l << " " << md << " " << r << endl;
        w = vector<int> (M , 0);
        dfs(U , V , 1);

        for(int i = l ; i <= md ; i ++)
            w[mp[{par[poss[i]] , poss[i]}]] = 1 ;

        toll2 = ask(w);

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



    }

    int s , t ;
    s = poss[l];


    swap(U , V);



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


    dfs(U , V , 1);

    toll2 = ask(w);

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

    va = B - A ;
    v2 = B * d - toll2 ;

    v2 /= va ;
    rest = d - v2 ;

  bfs(V);


    toll = toll2;
    poss.clear();

    for(int i = 0 ; i < n; i ++){
        if(i != U && ds[i] == v2 - 1 )poss.push_back(i);
    }


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

    while(l < r){

        md = (l + r ) / 2 ;

//cout << l << " " << md << " " << r << endl;
        w = vector<int> (M , 0);
        dfs(U , V , 1);

        for(int i = l ; i <= md ; i ++)
            w[mp[{par[poss[i]] , poss[i]}]] = 1 ;

        toll2 = ask(w);

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



    }

   t = poss[l];




  answer(s, t);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:142:38: warning: right operand of comma operator has no effect [-Wunused-value]
  142 |     l = 0 , r = poss.size() - 1 , md ;
      |                                      ^
highway.cpp:200:38: warning: right operand of comma operator has no effect [-Wunused-value]
  200 |     l = 0 , r = poss.size() - 1 , md ;
      |                                      ^
highway.cpp:129:9: warning: variable 'rest' set but not used [-Wunused-but-set-variable]
  129 |     int rest = d - v2 ;
      |         ^~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	3144 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	3272 KB	Output is correct
2	Correct	43 ms	5136 KB	Output is correct
3	Correct	615 ms	21324 KB	Output is correct
4	Correct	919 ms	21396 KB	Output is correct
5	Correct	713 ms	21316 KB	Output is correct
6	Correct	1370 ms	21952 KB	Output is correct
7	Correct	866 ms	21408 KB	Output is correct
8	Correct	885 ms	21224 KB	Output is correct
9	Correct	613 ms	21208 KB	Output is correct
10	Correct	491 ms	21316 KB	Output is correct
11	Correct	515 ms	22744 KB	Output is correct
12	Correct	562 ms	23808 KB	Output is correct
13	Correct	510 ms	23156 KB	Output is correct
14	Correct	571 ms	23272 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	5944 KB	Output is correct
2	Correct	65 ms	8736 KB	Output is correct
3	Correct	72 ms	11572 KB	Output is correct
4	Correct	351 ms	26512 KB	Output is correct
5	Correct	334 ms	26640 KB	Output is correct
6	Correct	373 ms	28416 KB	Output is correct
7	Correct	234 ms	29388 KB	Output is correct
8	Correct	357 ms	27312 KB	Output is correct
9	Correct	228 ms	27840 KB	Output is correct