Submission #423453

#	Time	Username	Problem	Language	Result	Execution time	Memory
423453		ja_kingy	Highway Tolls (IOI18_highway)	C++14	100 / 100	352 ms	13692 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
const int mxN = 90000;
int n, m, mn;
vector<pii> adj[mxN];

int qry(vector<int> &edges) {
    vector<int> w(m);
    for (int i: edges) w[i] = 1;
    return ask(w);
}

int bsearch(vector<int> edges, vector<int> extras){
    int lo = 0, hi = edges.size(), mid;
    while (hi != lo) {
        mid = lo+hi>>1;
        vector<int> q = extras;
        q.insert(q.end(), edges.begin(), edges.begin()+mid+1);
        if (qry(q) != mn) hi = mid;
        else lo = mid+1; 
    }
    return lo;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N;
    m = U.size();
    for (int i = 0; i < m; ++i) {
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }
    vector<int> all(m);
    iota(all.begin(), all.end(), 0);
    mn = ask(vector<int>(m));
    int fst = bsearch(all, {});
    queue<int> q;
    vector<int> seen(n), edge_in_tree(m), node_in_subtree(n), tree_edges, psubtree, ch(m);
    q.push(U[fst]);
    seen[U[fst]] = 1;
    while (q.size()) {
        int u = q.front(); q.pop();
        for (pii e: adj[u]) if (e.second >= fst && !seen[e.first]) {
            seen[e.first] = 1;
            q.push(e.first);
            if (node_in_subtree[u] || e.first == V[fst]) {
                node_in_subtree[e.first] = 1;
                psubtree.push_back(e.second);
            } else {
                tree_edges.push_back(e.second);
            }
            edge_in_tree[e.second] = 1;
            ch[e.second] = e.first;
        }
    }
    vector<int> extras;
    for (int i = 0; i < m; ++i) if (!edge_in_tree[i]) extras.push_back(i);
    reverse(psubtree.begin(), psubtree.end());
    reverse(tree_edges.begin(), tree_edges.end());
    int res = bsearch(tree_edges, extras);
    answer(ch[psubtree[bsearch(psubtree, extras)]], res == tree_edges.size() ? U[fst] : ch[tree_edges[res]]);
}

Compilation message (stderr)

highway.cpp: In function 'int bsearch(std::vector<int>, std::vector<int>)':
highway.cpp:19:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         mid = lo+hi>>1;
      |               ~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:63:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     answer(ch[psubtree[bsearch(psubtree, extras)]], res == tree_edges.size() ? U[fst] : ch[tree_edges[res]]);
      |                                                     ~~~~^~~~~~~~~~~~~~~~~~~~

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