Submission #497783

#	Time	Username	Problem	Language	Result	Execution time	Memory
497783		dxz05	Highway Tolls (IOI18_highway)	C++14	51 / 100	333 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) (x).begin(), (x).end()

const int MAXN = 1e5 + 3e2;

int N;
vector<pair<int, int>> g[MAXN];

void bfs(int root, vector<int> &d, vector<int> &edges, vector<int> &p){
    queue<int> q;
    vector<bool> used(N, false);
    used[root] = true;
    q.push(root);
    d[root] = 0;
    p[root] = -1;

    while (!q.empty()){
        int x = q.front(); q.pop();
        for (auto e : g[x]){
            int y = e.first, i = e.second;
            if (!used[y]){
                used[y] = true;
                q.push(y);
                d[y] = d[x] + 1;
                p[y] = i;
                edges.push_back(i);
            }
        }
    }
}

vector<int> vec;
vector<bool> allowed;

void dfs(int v, int p){
    vec.push_back(v);
    for (auto e : g[v]){
        int u = e.first;
        if (allowed[u] && u != p) dfs(u, v);
    }
}

void find_pair(int _N, vector<int> U, vector<int> V, int A, int B) {
    N = _N;
    int M = U.size();

    for (int i = 0; i < M; i++){
        g[U[i]].emplace_back(V[i], i);
        g[V[i]].emplace_back(U[i], i);
    }

    vector<int> w(M, 0);

    ll onlyA = ask(w);

    int ind = 0;

    int l = 0, r = M - 1;
    while (l <= r){
        int mid = (l + r) >> 1;
        fill(all(w), 0);
        for (int i = 0; i <= mid; i++) w[i] = 1;
        ll res = ask(w);
        if (res != onlyA){
            ind = mid;
            r = mid - 1;
        } else l = mid + 1;
    }

    int u = U[ind], v = V[ind];

//    cerr << u << ' ' << v << endl;

    vector<int> du(N), dv(N), pu(N), pv(N);
    vector<int> eu, ev;

    bfs(u,  du, eu, pu);
    bfs(v,  dv, ev, pv);

    pu[u] = pv[v] = ind;

    for (int i = 0; i < g[U[ind]].size(); i++){
        if (g[U[ind]][i].first == V[ind]) g[U[ind]].erase(g[U[ind]].begin() + i);
    }
    for (int i = 0; i < g[V[ind]].size(); i++){
        if (g[V[ind]][i].first == U[ind]) g[V[ind]].erase(g[V[ind]].begin() + i);
    }

    vector<int> a, b;
    for (int i = 0; i < N; i++){
        if (du[i] < dv[i]) a.push_back(i);
        if (dv[i] < du[i]) b.push_back(i);
    }

    allowed.assign(N, false);
    for (int i : a) allowed[i] = true;
    dfs(u, u);
    a = vec;

    vec.clear();
    fill(all(allowed), false);
    for (int i : b) allowed[i] = true;
    dfs(v, v);
    b = vec;

//    cerr << endl;
//    for (int x : a) cerr << x << ' ' << pu[x] << endl; cerr << endl;
//    for (int x : b) cerr << x << ' ' << pv[x] << endl; cerr << endl;

    int S = -1, T = -1;

    l = 0, r = a.size() - 1;
    while (l <= r){
        int mid = (l + r) >> 1;

        fill(all(w), 1);
        w[ind] = 0;
        for (int i = 0; i <= mid; i++) w[pu[a[i]]] = 0;
        for (int i : b) w[pv[i]] = 0;

        if (ask(w) == onlyA){
            S = a[mid];
            r = mid - 1;
        } else l = mid + 1;
    }

    l = 0, r = b.size() - 1;
    while (l <= r){
        int mid = (l + r) >> 1;

        fill(all(w), 1);
        w[ind] = 0;
        for (int i = 0; i <= mid; i++) w[pv[b[i]]] = 0;
        for (int i : a) w[pu[i]] = 0;

//        cerr << "mid = " << mid << endl;
//        for (int x : w) cerr << x << ' '; cerr << endl << endl;

        if (ask(w) == onlyA){
            T = b[mid];
            r = mid - 1;
        } else l = mid + 1;
    }

//    cerr << S << ' ' << T << endl;

    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < g[U[ind]].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~
highway.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < g[V[ind]].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~

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