Submission #349030

#	Time	Username	Problem	Language	Result	Execution time	Memory
349030		milleniumEeee	Highway Tolls (IOI18_highway)	C++17	51 / 100	247 ms	23764 KiB

highway

#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 ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m;
vector <pair<int, int>> G[MAXN]; // обычный граф
vector <pair<int, int>> tree[MAXN]; // дерево
int edge[MAXN][2];
bool used[MAXN];
ll costa, costb;
ll diametr;
ll min_path, max_path;
int ROOT, SUB_S;
vector <int> bfs_edges; // already sorted by id

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

void create_tree() {
    // найти ребро на пути S -> T
    vector <int> w(m);
    for (int i = 0; i < m; i++) {
        w[i] = 0;
    }
    w[0] = 1;
    ll cur_cost = ask(w);
    int root = -1;
    int sub = -1;
    int l = -1, r = m - 1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        for (int i = 0; i < m; i++) {
            w[i] = 0;
        }
        for (int i = 0; i <= mid; i++) {
            w[i] = 1;
        }
        cur_cost = ask(w);
        if (cur_cost == min_path) {
            l = mid;
        } else {
            r = mid;
        }
    }
    root = edge[r][0];
    sub = edge[r][1];
    queue <int> q;
    vector <int> dist(MAXN, -1);
    dist[root] = 0;
    q.push(root);
    ROOT = root;
    SUB_S = sub;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (pii to : G[v]) {
            if (dist[to.fr] == -1) {
                used[to.sc] = true;
                bfs_edges.pb(to.sc);
                tree[v].pb({to.fr, to.sc});
                tree[to.fr].pb({v, to.sc});
                dist[to.fr] = dist[v] + 1;
                q.push(to.fr);
            }
        }
    }
}

int pr[MAXN];
int d[MAXN];
void calc(int v, int par, int len) {
    pr[v] = par;
    d[v] = len;
    for (pii to : tree[v]) {
        if (to.fr != par) {
            calc(to.fr, v, len + 1);
        }
    }
}

void dfs(int v, int par, int len, vector <pii> &possible) {
    for (pii to : tree[v]) {
        if (to.fr != par) {
            if (len + 1 == diametr) {
                possible.pb({to.fr, to.sc});
            }
            dfs(to.fr, v, len + 1, possible);
        }
    }
}

void find_pair(int N, vector<int> U, vector<int> V, int AA, int BB) {
    m = szof(U);
    n = N;
    costa = AA;
    costb = BB;
    min_path = get_min_path(); // 1 q
    diametr = min_path / costa;
    max_path = diametr * costb;
    for (int i = 0; i < m; i++) {
        int x, y;
        x = U[i];
        y = V[i];
        edge[i][0] = x;
        edge[i][1] = y;
        G[x].pb({y, i});
        G[y].pb({x, i});
    }
    create_tree(); // log(n) queries
    int l = -1, r = szof(bfs_edges) - 1;
    vector <int> w(m);
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        for (int i = 0; i < m; i++) {
            w[i] = 1;
        }
        for (int el : bfs_edges) {
            w[el] = 0;
        }
        for (int i = 0; i <= mid; i++) {
            w[bfs_edges[i]] = 1;
        }
        ll cur_cost = ask(w);
        if (cur_cost != max_path) {
            l = mid;
        } else {
            r = mid;
        }
    }
    calc(ROOT, -1, 0);
    int last_edge = bfs_edges[r];
    int x = edge[last_edge][0], y = edge[last_edge][1];
    int my_s = (d[x] > d[y] ? x : y);
    vector <pii> possible;
    dfs(my_s, -1, 0, possible);
    // possible.fr vertex
    // possible.sc edge real id
    l = 0, r = szof(possible) - 1;
    while (l != r) {
        int mid = (l + r) >> 1;
        for (int i = 0; i < m; i++) {
            w[i] = 1;
        }
        for (int el : bfs_edges) {
            w[el] = 0;
        }
        for (int i = l; i <= mid; i++) {
            w[possible[i].sc] = 1;
        }
        ll cur_cost = ask(w);
        if (cur_cost == min_path) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    answer(my_s, possible[l].fr);
}

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