Submission #349131

#	Time	Username	Problem	Language	Result	Execution time	Memory
349131		milleniumEeee	Highway Tolls (IOI18_highway)	C++17	90 / 100	722 ms	37948 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;
vector <int> bfs_edges[3]; // already sorted by id
map <pii, int> id;

int REAL_S = 6122;
int REAL_T = 485;

//int N, M, A, B, S, T;
//vector <int> U, V;
//vector <vector<pii>> graph;
//long long ask(const std::vector<int> &w) {
  //std::vector<bool> visited(N, false);
  //std::vector<long long> current_dist(N, INF);
  //std::queue<int> qa, qb;
  //qa.push(S);
  //current_dist[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 == 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 + A) {
            //current_dist[vv] = d + A;
            //qa.push(vv);
          //}
        //} else {
          //if (current_dist[vv] > d + B) {
            //current_dist[vv] = d + B;
            //qb.push(vv);
          //}
        //}
      //}
    //}
  //}
  //return -1;
//}
 
 
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;
        }
    }
    ROOT = edge[r][0];
    SUB_S = edge[r][1];
    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);
    
    assert(id.count(mk(root, SUB_S)));
    
    for (int i = 1; i < szof(G[root]); i++) {
        if (G[root][i].fr == SUB_S) {
            swap(G[root][0], G[root][i]);
            break;
        }
    }
    
    //int sub_id = id[mk(root, SUB_S)];
    //used[SUB_S] = true;
    //BFS_EDGES.pb(sub_id);
    //tree[root].pb({SUB_S, sub_id});
    //tree[sub_id].pb({SUB_S, root});
    //dist[SUB_S] = 1;
    //q.push(SUB_S);
    
    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];
int tin[MAXN];
int tout[MAXN];
int tiktak = 0;

int parent[MAXN];
bool color[MAXN];

vector <int> cycle;

bool find_cycle(int v, int par) {
    color[v] = 1;
    parent[v] = par;
    for (pii to : tree[v]) {
        if (to.fr == par) {
            continue;
        }
        if (color[to.fr]) {
            int fn = v;
            while (fn != to.fr) {
                cycle.pb(fn);
                fn = parent[fn];
            }
            cycle.pb(to.fr);
            return true;
        } else {
            bool f = find_cycle(to.fr, v);
            if (f) {
                return true;
            }
        }
    }
    return false;
}

void calc(int v, int par, int len) {
    tin[v] = ++tiktak;
    d[v] = len;
    for (pii to : tree[v]) {
        if (to.fr != par) {
            calc(to.fr, v, len + 1);            
        }
    }
    tout[v] = tiktak;
}
bool father(int a, int b) {
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}
vector <int> subtree[3];

void dfs(int v, int par) {
    if (father(SUB_S, v)) {
        subtree[1].pb(v);
    } else {
        subtree[2].pb(v);
    }
    for (pii to : tree[v]) {
        if (to.fr != par) {
            dfs(to.fr, v);
        }
    }
}

int find_ans(int cur_root, vector <int> cur_bfs_edges) {
    if (cur_bfs_edges.empty()) {
        return cur_root;
    }
    int l = 0, r = szof(cur_bfs_edges);
    vector <int> w(m, 1);
    // check for not root
    for (int el : BFS_EDGES) {
        w[el] = 0;
    }
    for (int el : cur_bfs_edges) { 
        w[el] = 1;
    }
    
    ll wtf_cost = ask(w);
    if (wtf_cost == min_path) {
        return cur_root;
    }
    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(cur_bfs_edges); i++) {
            w[cur_bfs_edges[i]] = 1;
        }
        ll cur_cost = ask(w);
        if (cur_cost == min_path) {
            r = mid;
        } else {
            l = mid;
        }
    }
    int x = edge[cur_bfs_edges[l]][0];
    int y = edge[cur_bfs_edges[l]][1];
    
    vector <int> other(m);
    for (int i = 0; i < m; i++) {
        other[i] = 1;
    }
    for (int el : BFS_EDGES) {
        other[el] = 0;
    }
    for (int i = 0; i < m; i++) {
        other[i] = 1;
    }
    for (int el : BFS_EDGES) {
        other[el] = 0;
    }
    for (int i = r - 1; i < szof(cur_bfs_edges); i++) {
        other[cur_bfs_edges[i]] = 1;
    }
    return (d[x] > d[y] ? x : y);
}

void find_pair(int N, vector<int> U, vector<int> V, int AA, int BB) {
    //cout << "ok1" << endl;
    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];
        id[{x, y}] = i;
        id[{y, x}] = i;
        edge[i][0] = x;
        edge[i][1] = y;
        G[x].pb({y, i});
        G[y].pb({x, i});
    }
    
    //cout << "ok2" << endl;
    
    int s, t;
    int root = find_root(); // log(n)
    //cout << "ok3" << endl;
    create_tree(root);
    //cout << "ok4" << endl;
    
    //find_cycle(root, -1);
    //for (int el : cycle) {
        //cout << el << " ";
    //}
    //cout << "fucking cycle " << endl;
    
    
    calc(root, -1, 0);
    //cout << "ok5" << endl;
    dfs(root, -1);
    //cout << "ok6" << endl;
    sort(all(subtree[1]));
    sort(all(subtree[2]));
    
    
    auto exist = [&](vector <int> &vec, int x) {
        bool ok = binary_search(all(vec), x);
        return ok;
    };
    for (int el : BFS_EDGES) {
        int x = edge[el][0];
        int y = edge[el][1];
        if ((x == ROOT && y == SUB_S) || (x == SUB_S && y == ROOT)) {
            continue;
        }
        if (exist(subtree[1], x)) {
            bfs_edges[1].pb({id[{x, y}]});
        } else {
            bfs_edges[2].pb({id[{x, y}]});
        }
    }
    s = find_ans(SUB_S, bfs_edges[1]); // log(n) - 1
    t = find_ans(ROOT, bfs_edges[2]); // log(n) - 1
    answer(s, t);
}

//signed main() {
    //cin >> N;
    //cin >> M;
    //cin >> A;
    //cin >> B;
    //cin >> S;
    //cin >> T;
    //U.resize(M);
    //V.resize(M);
    //graph.assign(N, std::vector<std::pair<int, int>>());
    //for (int i = 0; i < M; ++i) {
        //cin >> U[i];
        //cin >> V[i];
        //graph[U[i]].push_back({V[i], i});
        //graph[V[i]].push_back({U[i], i});
    //}
    //find_pair(N, U, V, A, B);
//}

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