Submission #433463

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
433463	2021-06-19T20:39:02 Z	ioi	Highway Tolls (IOI18_highway)	C++14	13 / 100	828 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];

   // cout << "rest " << rest << endl;





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


    dfs(V , U , 1);
    w[mp[{U , V}]] = 1 ;
    toll2 = ask(w);

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

    // rest

  bfs(U);


    toll = toll2;
    poss.clear();
    ds[U] = 0 ;
    for(int i = 0 ; i < n; i ++){
        if(i != V && ds[i] == rest  && vis[i] == vid )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(V , U , 1);

        for(int i = l ; i <= md ; i ++)
            w[mp[{par[poss[i]] , poss[i]}]] = 1 ;
        w[mp[{U , V}]] = 1 ;
        toll2 = ask(w);
       // cout << "toll  " << toll << " " <<  toll2 << endl ;
        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:198:38: warning: right operand of comma operator has no effect [-Wunused-value]
  198 |     l = 0 , r = poss.size() - 1 , md ;
      |                                      ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	3016 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	4 ms	3272 KB	Output is correct
2	Correct	38 ms	5064 KB	Output is correct
3	Correct	552 ms	21392 KB	Output is correct
4	Correct	828 ms	21412 KB	Output is correct
5	Correct	722 ms	21412 KB	Output is correct
6	Correct	443 ms	21264 KB	Output is correct
7	Correct	809 ms	21420 KB	Output is correct
8	Correct	715 ms	21312 KB	Output is correct
9	Correct	534 ms	21224 KB	Output is correct
10	Correct	456 ms	21516 KB	Output is correct
11	Correct	498 ms	22700 KB	Output is correct
12	Correct	545 ms	23920 KB	Output is correct
13	Correct	402 ms	23168 KB	Output is correct
14	Correct	560 ms	23376 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	5920 KB	Output is correct
2	Correct	48 ms	8688 KB	Output is correct
3	Correct	70 ms	11576 KB	Output is correct
4	Correct	219 ms	26272 KB	Output is correct
5	Correct	217 ms	26240 KB	Output is correct
6	Correct	217 ms	27764 KB	Output is correct
7	Correct	220 ms	29148 KB	Output is correct
8	Correct	214 ms	26964 KB	Output is correct
9	Correct	168 ms	27288 KB	Output is correct