Submission #735247

#	Time	Username	Problem	Language	Result	Execution time	Memory
735247		pls33	Highway Tolls (IOI18_highway)	C++17	0 / 100	14 ms	1804 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)>;

void find_vertex(int l, int r, int &b,
                 vi32 &query, vi32 order,
                 int64_t cost, vi32 &distance,
                 vi32 &U, vi32 &V)
{
    if (b != -1 || l == r)
    {
        return;
    }

    fill(query.begin(), query.end(), 0);

    int mid = (l + r) / 2;

    for (int i = l; (r - l == 1) ? i < r : i < mid; i++)
    {
        query[order[i]] = 1;
    }

    int64_t answer = ask(query);
    if (r - l == 1)
    {
        if (answer > cost)
        {
            int id = order[l];
            b = (distance[U[id]] > distance[V[id]]) ? U[id] : V[id];
        }
        return;
    }

    find_vertex(l, mid, b, query, order, cost, distance, U, V);
    find_vertex(mid, r, b, query, order, cost, distance, U, V);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    vvp32 adj(N);
    A *= B;
    for (int i = 0; i < (int)U.size(); 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);
    // int count = int(cost / A);

    vi32 order;

    queue<int> q;
    state_t visited;
    vi32 distance(N);

    q.push(0);
    visited[0] = 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());

    int b = -1;
    vi32 query(order.size());
    find_vertex(0, (int)order.size(), b, query, order, cost, distance, U, V);

    answer(0, 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: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31