Submission #348606

#	Time	Username	Problem	Language	Result	Execution time	Memory
348606		milleniumEeee	Highway Tolls (IOI18_highway)	C++17	5 / 100	432 ms	262148 KiB

highway

// answer(A, B);
// ask(vector) => cost
#include "highway.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mk make_pair
#define pb push_back
#define ll long long
using namespace std;

const int MAXN = 130005;
const int INF = 0x3f3f3f3f;

int from[MAXN], to[MAXN];
vector <int> g[MAXN];
int dist[MAXN];
int pr[MAXN];
int costa, costb;
int min_path;
int diametr;
int n, m;

map <pii, int> id;
//vector <pii> graph[MAXN];
//int REAL_S, REAL_T;

//int ask(vector <int> w) {
    //vector<bool> visited(n, false);
    //vector<long long> current_dist(n, INF);
  //queue<int> qa, qb;
  //qa.push(REAL_S);
  //current_dist[REAL_S] = 0;
  //while (!qa.empty() || !qb.empty()) {
    //int v;
    //if (qb.empty() || (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
      //v = qa.front();
      //qa.pop();
    //} else {
      //v = qb.front();
      //qb.pop();
    //}
    //if (visited[v]) {
      //continue;
    //}
    //visited[v] = true;
    //long long d = current_dist[v];
    //if (v == REAL_T) {
      //return d;
    //}
    //for (auto e : graph[v]) {
      //int vv = e.first;
      //int ei = e.second;
      //if (!visited[vv]) {
        //if (w[ei] == 0) {
          //if (current_dist[vv] > d + costa) {
            //current_dist[vv] = d + costa;
            //qa.push(vv);
          //}
        //} else {
          //if (current_dist[vv] > d + costb) {
            //current_dist[vv] = d + costb;
            //qb.push(vv);
          //}
        //}
      //}
    //}
  //}
//}


void make_edge(int x, int y) {
    g[x].pb(y);
    g[y].pb(x);
}

int find_middle_edge() {
    int l = 0, r = m - 1;
    vector <int> w(m);
    while (l != r) {
        int mid = (l + r) >> 1;
        for (int i = l; i <= r; i++) {
            if (i <= mid) {
                w[i] = 1;
            } else {
                w[i] = 0;
            }
        }
        int cur_cost = ask(w);
        if (cur_cost != min_path) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

int get_min_path() {
    vector <int> w(m);
    for (int i = 0; i < m; i++) {
        w[i] = 0;
    }
    ll cur_cost = ask(w);
    return ask(w);
}

void dfs(int v, int par, int len, vector <int> &s_sub) {
    for (int to : g[v]) {
        if (to != par) {
            s_sub.pb(id[{v, to}]);
            dfs(to, v, len + 1, s_sub);
        }
    }
}

void calc_dist_and_pr(int v, int par, int len) {
    dist[v] = len;
    pr[v] = par;
    for (int to : g[v]) {
        if (to != par) {
            calc_dist_and_pr(to, v, len + 1);
        }
    }
}

int find_s(vector <int> s_sub) {
    //cout << "s_sub: " << endl;
    //for (int el : s_sub) {
        //cout << el << " ";
    //}cout << endl;
    vector <int> w(m, 0);
    for (int el : s_sub) {
        w[el] = 1;
    }
    int cost = ask(w);
    int root_to_s = (cost - min_path) / (costb - costa);
    
    //cout << "root_to_s: " << root_to_s << endl;
    
    vector <int> possible;
    for (int i = 0; i < n; i++) {
        if (dist[i] == root_to_s) {
            //cout << "vertex: " << i << endl;
            //cout << "                " << i << " " << pr[i] << endl;
            possible.pb(id[{i, pr[i]}]);
        }
    }
    
    //cout << "possible: " << endl;
    //for (int el : possible) {
        //cout << el << " ";
    //}cout << "\n\n";
    
    int l = 0, r = szof(possible) - 1;
    while (l != r) {
        int mid = (l + r) >> 1;
        for (int i = 0; i < m; i++) {
            w[i] = 0;
        }
        for (int i = l; i <= mid; i++) {
            w[possible[i]] = 1;
        }
        int cur_cost = ask(w);
        if (cur_cost != min_path) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    int need_edge = possible[l];
    if (dist[from[need_edge]] == root_to_s) {
        return from[need_edge];
    } else {
        return to[need_edge];
    }
}

void find_pair(int N, vector<int> U, vector<int> V, int AA, int BB) {
    costa = AA, costb = BB;
    m = U.size();
    n = N;
    for (int i = 0; i < m; i++) {
        from[i] = U[i];
        to[i] = V[i];
        id[{from[i], to[i]}] = i;
        id[{to[i], from[i]}] = i;
        make_edge(from[i], to[i]);
        //graph[U[i]].push_back({V[i], i});
        //graph[V[i]].push_back({U[i], i});
    }
    
    //cout << "adad" << endl;
    
    min_path = get_min_path();
    diametr = min_path / costa;
    int mid_edge = find_middle_edge();
    int root = from[mid_edge];
    int need_sub = to[mid_edge];
    
    //cout << "root: " << root << endl;
    //cout << "sub: " << need_sub << endl;
    
    vector <int> s_sub;
    s_sub.pb(id[{root, need_sub}]);
    memset(dist, -1, sizeof(dist));
    calc_dist_and_pr(need_sub, root, 1);
    dist[root] = 0;
    dfs(need_sub, root, 1, s_sub);
    int SS = find_s(s_sub);
    
    //cout << "my S: " << SS << endl;
    
    memset(dist, -1, sizeof(dist));
    calc_dist_and_pr(SS, -1, 0);
    vector <int> possible;
    for (int i = 0; i < n; i++) {
        if (dist[i] == diametr) {
            possible.pb(id[{i, pr[i]}]);
        }
    }
    int l = 0, r = szof(possible) - 1;
    vector <int> w(m);
    while (l != r) {
        int mid = (l + r) >> 1;
        for (int i = 0; i < m; i++) {
            w[i] = 0;
        }
        for (int i = l; i <= mid; i++) {
            w[possible[i]] = 1;
        }
        int cur_cost = ask(w);
        if (cur_cost != min_path) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    int need_edge = possible[l];
    int TT;
    if (dist[from[need_edge]] == diametr) {
        TT = from[need_edge];
    } else {
        TT = to[need_edge];
    }
    if (SS > TT) {
        swap(SS, TT);
    }
    answer(SS, TT);
}

//signed main() {
    //int n, m, a, b, s, t;
    //cin >> n >> m >> a >> b >> s >> t;
    //REAL_S = s, REAL_T = t;
    //vector <int> U, V;
    //U.resize(m);
    //V.resize(m);
    //for (int i = 0; i < m; i++) {
        //cin >> U[i] >> V[i];
    //}
    //find_pair(n, U, V, a, b);
//}

/*
5 4 3 13 0 3
4 1
2 0
1 2
3 1
*/

Compilation message (stderr)

highway.cpp: In function 'int get_min_path()':
highway.cpp:108:8: warning: unused variable 'cur_cost' [-Wunused-variable]
  108 |     ll cur_cost = ask(w);
      |        ^~~~~~~~

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