Submission #348521

#	Time	Username	Problem	Language	Result	Execution time	Memory
348521		milleniumEeee	Highway Tolls (IOI18_highway)	C++14	Compilation error	0 ms	0 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
using namespace std;

const int MAXN = 90005;
int u[MAXN], v[MAXN];
vector <int> g[MAXN];
int costa, costb;
int n, m;
int min_path;
int diametr;

map <pii, int> id;

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;
    }
    return ask(w);
}

int dist[MAXN];
int pr[MAXN];
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) {
    vector <int> w(n, 0);
    for (int el : s_sub) {
        w[el] = 1;
    }
    int cost = ask(w);
    int root_to_s = (cost - min_path) / (B - A);
    vector <int> possible;
    for (int i = 0; i < n; i++) {
        if (dist[i] == root_to_s) {
            possible.pb(id[{i, pr[i]}]);
        }
    }
    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[u[need_edge]] == root_to_s) {
        return u[need_edge];
    } else {
        return v[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;
    min_path = get_min_path();
    diametr = min_path / costa;
    for (int i = 0; i < m; i++) {
        u[i] = U[i];
        v[i] = V[i];
        id[{u[i], v[i]}] = i;
        id[{v[i], u[i]}] = i;
        make_edge(u[i], v[i]);
    }
    int mid_edge = find_middle_edge();
    int root = u[mid_edge];
    int need_sub = v[mid_edge];
    vector <int> s_sub;
    s_sub.pb(id[{root, need_sub}]);
    memset(dist, -1, sizeof(dist));
    calc_dist_and_pr(root, -1, 0);
    dfs(need_sub, root, 1, s_sub);
    int S = find_s(s_sub);
    calc_dist_and_pr(S, -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];
    if (dist[u[need_edge]] == diametr) {
        T = u[need_edge];
    } else {
        T = v[need_edge];
    }
    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'int find_s(std::vector<int>)':
highway.cpp:87:42: error: 'B' was not declared in this scope
   87 |     int root_to_s = (cost - min_path) / (B - A);
      |                                          ^
highway.cpp:87:46: error: 'A' was not declared in this scope
   87 |     int root_to_s = (cost - min_path) / (B - A);
      |                                              ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:166:9: error: 'T' was not declared in this scope
  166 |         T = u[need_edge];
      |         ^
highway.cpp:168:9: error: 'T' was not declared in this scope
  168 |         T = v[need_edge];
      |         ^
highway.cpp:170:15: error: 'T' was not declared in this scope
  170 |     answer(S, T);
      |               ^