Submission #433453

#	Time	Username	Problem	Language	Result	Execution time	Memory
433453		ioi	통행료 (IOI18_highway)	C++14	13 / 100	1370 ms	262148 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];

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 (stderr)

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
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31