Submission #443968

#	Time	Username	Problem	Language	Result	Execution time	Memory
443968		two_sides	Highway Tolls (IOI18_highway)	C++17	0 / 100	18 ms	1256 KiB

highway

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

using namespace std;

void find_pair(int N, vector<int> U,
vector<int> V, int A, int B) {
    int M = U.size();
    int lo = 0, hi = M - 1, pos;
    vector<int> w(M), ord(M, -1), idx(N);
    vector<int> du(N, -1), dv(N, -1);
    int init = ask(w);
    while (lo <= hi) {
        int mi = (lo + hi) / 2;
        for (int i = 0; i < M; i++)
            w[i] = i <= mi;
        if (ask(w) > init) {
            pos = mi; hi = mi - 1;
        } else lo = mi + 1;
    }
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[U[i]].push_back(i);
        adj[V[i]].push_back(i);
    }
    queue<int> que;
    que.push(U[pos]); du[U[pos]] = 0;
    while (que.size()) {
        int u = que.front(); que.pop();
        for (auto e : adj[u]) {
            int v = u ^ U[e] ^ V[e];
            if (du[v] < 0) {
                du[v] = du[u] + 1;
                que.push(v);
            }
        }
    }
    que.push(V[pos]); dv[V[pos]] = 0;
    while (que.size()) {
        int u = que.front(); que.pop();
        for (auto e : adj[u]) {
            int v = u ^ U[e] ^ V[e];
            if (dv[v] < 0) {
                dv[v] = dv[u] + 1;
                que.push(v);
            }
        }
    }
    vector<int> vis(N);
    int cnt = 0;
    que.push(U[pos]); vis[U[pos]] = 1;
    pair<int, int> ans(U[pos], V[pos]);
    while (que.size()) {
        int u = que.front(); que.pop();
        for (auto e : adj[u]) {
            int v = u ^ U[e] ^ V[e];
            if (du[v] < dv[v]) {
                if (!vis[v]) {
                    idx[ord[e] = cnt++] = e;
                    vis[v] = 1; que.push(v);
                } else if (du[v] == du[u] + 1)
                    ord[e] = N;
            } else ord[e] = N;
        }
    }
    lo = 0; hi = cnt - 1;
    while (lo <= hi) {
        int mi = (lo + hi) / 2;
        for (int i = 0; i < M; i++)
            w[i] = ord[i] >= mi;
        if (ask(w) > init) {
            if (du[U[idx[mi]]] < du[V[idx[mi]]])
                ans.first = V[idx[mi]];
            else ans.first = U[idx[mi]];
            lo = mi + 1;
        } else hi = mi - 1;
    }
    cnt = 0;
    que.push(V[pos]); vis[V[pos]] = 0;
    fill(ord.begin(), ord.end(), -1);
    while (que.size()) {
        int u = que.front(); que.pop();
        for (auto e : adj[u]) {
            int v = u ^ U[e] ^ V[e];
            if (dv[v] < du[v]) {
                if (!vis[v]) {
                    idx[ord[e] = cnt++] = e;
                    vis[v] = 1; que.push(v);
                } else if (dv[v] == dv[u] + 1)
                    ord[e] = N;
            } else ord[e] = N;
        }
    }
    lo = 0; hi = cnt - 1;
    while (lo <= hi) {
        int mi = (lo + hi) / 2;
        for (int i = 0; i < M; i++)
            w[i] = ord[i] >= mi;
        if (ask(w) > init) {
            if (dv[U[idx[mi]]] < dv[V[idx[mi]]])
                ans.second = V[idx[mi]];
            else ans.second = U[idx[mi]];
            lo = mi + 1;
        } else hi = mi - 1;
    }
    answer(ans.first, ans.second);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:27:19: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |     que.push(U[pos]); du[U[pos]] = 0;
      |                   ^

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