Submission #349090

#	Time	Username	Problem	Language	Result	Execution time	Memory
349090		milleniumEeee	Highway Tolls (IOI18_highway)	C++17	90 / 100	372 ms	19592 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;
}
 
int find_root() {
    vector <int> w(m);
    for (int i = 0; i < m; i++) {
        w[i] = 0;
    }
    w[0] = 1;
    ll cur_cost;
    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;
        }
    }
    return edge[r][0];
}
 
void create_tree(int root) {
    bfs_edges.clear();
    memset(used, 0, sizeof(used));
    for (int i = 0; i < MAXN; i++) {
        tree[i].clear();
    }
    // найти ребро на пути S -> T
    queue <int> q;
    vector <int> dist(MAXN, -1);
    dist[root] = 0;
    q.push(root);
    ROOT = root;
    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 d[MAXN];
void calc(int v, int par, int len) {
    d[v] = len;
    for (pii to : tree[v]) {
        if (to.fr != par) {
            calc(to.fr, v, len + 1);            
        }
    }
}
 
int find_ans() {
    int l = 0, r = szof(bfs_edges);
    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 = mid; i < szof(bfs_edges); i++) {
            w[bfs_edges[i]] = 1;
        }
        ll cur_cost = ask(w);
        if (cur_cost == min_path) {
            r = mid;
        } else {
            l = mid;
        }
    }
    int need_edge = bfs_edges[l];
    int px = edge[need_edge][0], py = edge[need_edge][1];
    return (d[px] > d[py] ? px : py);
}
 
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});
    }
    int root = find_root();
    create_tree(root); // log(n)
    calc(root, -1, 0);
    int s = find_ans(); // log(n)
    create_tree(s);
    calc(s, -1, 0);
    int t = find_ans();
    answer(s, t);
}

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