Submission #736476

#	Time	Username	Problem	Language	Result	Execution time	Memory
736476		pls33	Highway Tolls (IOI18_highway)	C++17	7 / 100	152 ms	8756 KiB

highway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifndef _AAAAAAAAA
#include "highway.h"
#else
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B);
long long ask(const std::vector<int> &w);
void answer(int s, int t);
#endif

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
template <typename F>
void _debug(F f)
{
    f();
}

#ifndef _AAAAAAAAA
#define debug(x)
#else
#define debug(x) _debug(x)
#endif
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion

using state_t = bitset<size_t(13 * 1e4)>;

int find_blocking_edge(vi32 &order, int64_t cost, int edge_count)
{
    if (!order.size())
    {
        return -1;
    }

    int b = 0;
    bool asked = false;
    vi32 query(edge_count);

    for (int bit = 31 - __builtin_clz((int)order.size()); bit >= 0; bit--)
    {
        int cur = b + (1 << bit);
        if (cur >= (int)query.size())
        {
            continue;
        }

        for (int i = 0; i < (int)order.size(); i++)
        {
            query[order[i]] = i <= cur;
        }

        if (ask(query) > cost)
        {
            continue;
        }

        asked = true;

        b = cur;
    }

    return order[b + int(asked)];
}

void find_bfs_order(int start, int blocked, vvp32 &adj, vi32 &order, vi32 &distance)
{
    queue<int> q;
    state_t visited;

    q.push(start);
    visited[start] = true;
    if (blocked != -1)
    {
        visited[blocked] = true;
    }

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        for (auto &[next, index] : adj[cur])
        {
            if (visited[next])
            {
                continue;
            }

            order.push_back(index);
            q.push(next);
            visited[next] = true;
            distance[next] = distance[cur] + 1;
        }
    }

    reverse(order.begin(), order.end());
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    const int edge_count = (int)U.size();

    vvp32 adj(N);
    A *= B;
    for (int i = 0; i < edge_count; i++)
    {
        int a = U[i], b = V[i];

        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
    }

    vi32 sample(U.size());
    int64_t cost = ask(sample);

    vi32 order(U.size());
    iota(order.begin(), order.end(), 0);
    reverse(order.begin(), order.end());

    int initial = find_blocking_edge(order, cost, edge_count);

    int a = U[initial], b = V[initial];

    vi32 distance(N);

    order.clear();
    find_bfs_order(a, b, adj, order, distance);
    int left = find_blocking_edge(order, cost, edge_count);

    order.clear();
    find_bfs_order(b, a, adj, order, distance);
    int right = find_blocking_edge(order, cost, edge_count);

    if (left != -1)
    {
        a = (distance[U[left]] > distance[V[left]]) ? U[left] : V[left];
    }
    if (right != -1)
    {
        b = (distance[U[right]] > distance[V[right]]) ? U[right] : V[right];
    }
    answer(a, b);
}

#ifdef _AAAAAAAAA

namespace
{

    constexpr int MAX_NUM_CALLS = 100;
    constexpr long long INF = 1LL << 61;

    int N, M, A, B, S, T;
    std::vector<int> U, V;
    std::vector<std::vector<std::pair<int, int>>> graph;

    bool answered, wrong_pair;
    int num_calls;

    int read_int()
    {
        int x;
        if (scanf("%d", &x) != 1)
        {
            fprintf(stderr, "Error while reading input\n");
            exit(1);
        }
        return x;
    }

    void wrong_answer(const char *MSG)
    {
        printf("Wrong Answer: %s\n", MSG);
        exit(0);
    }

} // namespace

long long ask(const std::vector<int> &w)
{
    if (++num_calls > MAX_NUM_CALLS)
    {
        wrong_answer("more than 100 calls to ask");
    }
    if (w.size() != (size_t)M)
    {
        wrong_answer("w is invalid");
    }
    for (size_t i = 0; i < w.size(); ++i)
    {
        if (!(w[i] == 0 || w[i] == 1))
        {
            wrong_answer("w is invalid");
        }
    }

    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;
}

void answer(int s, int t)
{
    if (answered)
    {
        wrong_answer("answered not exactly once");
    }

    if (!((s == S && t == T) || (s == T && t == S)))
    {
        wrong_pair = true;
    }

    answered = true;
}

int main()
{
    freopen("greitkeliai.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
    N = read_int();
    M = read_int();
    A = read_int();
    B = read_int();
    S = read_int();
    T = read_int();
    U.resize(M);
    V.resize(M);
    graph.assign(N, std::vector<std::pair<int, int>>());
    for (int i = 0; i < M; ++i)
    {
        U[i] = read_int();
        V[i] = read_int();
        graph[U[i]].push_back({V[i], i});
        graph[V[i]].push_back({U[i], i});
    }

    answered = false;
    wrong_pair = false;
    num_calls = 0;
    find_pair(N, U, V, A, B);
    if (!answered)
    {
        wrong_answer("answered not exactly once");
    }
    if (wrong_pair)
    {
        wrong_answer("{s, t} is wrong");
    }
    printf("Accepted: %d\n", num_calls);
    return 0;
}
#endif

Compilation message (stderr)

highway.cpp:15: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
   15 | #pragma region dalykai
      | 
highway.cpp:50: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   50 | #pragma endregion
      |

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