Submission #743703

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

// kelinta briauna keicia trumpiausia kelia??
int find_blocking_edge(int64_t cost, int edge_count)
{
    vi32 query(edge_count);

    int low = 0, high = edge_count - 1;
    while (low != high)
    {
        int mid = (low + high) / 2;
        for (int i = 0; i < edge_count; i++)
        {
            query[i] = i <= mid;
        }

        int64_t new_cost = ask(query);
        if (new_cost > cost)
        {
            high = mid;
        }
        else
        {
            low = mid + 1;
        }
    }

    return low;
}

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

    q.push(start);
    visited[start] = true;
    visited[blocked] = true;

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

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

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

int find_end_edge(vp32 &order, int64_t cost, int edge_count)
{
    vi32 query(edge_count);

    int low = -1, high = (int)order.size() - 1;
    while (low != high)
    {
        int mid = (low + high + 1) / 2;

        // blokuojam ne medzio, o nereikalingas briaunas
        fill(query.begin(), query.end(), 1);
        for (int i = 0; i < (int)order.size(); i++)
        {
            query[order[i].first] = 0;
        }

        int64_t new_cost = ask(query);
        if (new_cost > cost)
        {
            low = mid;
        }
        else
        {
            high = mid - 1;
        }
    }

    return low;
}

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

    vvp32 adj(N);
    for (int i = 0; i < edge_count; i++)
    {
        // printf("%d -- %d [label=\"%d\"]\n", U[i], V[i], 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 initial = find_blocking_edge(cost, edge_count);
    int a = U[initial], b = V[initial];

    if (cost == A)
    {
        answer(a, b);
        return;
    }

    for (int i = 0; i < 2; i++)
    {
        vp32 order;
        vi32 distance(N, 0);
        find_bfs_order(a, b, adj, order, distance);
        int end = find_end_edge(order, cost, edge_count);
        a = (end == -1) ? a : order[end].second;

        swap(a, b);
    }

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

    printf("\n----------------\ngautas atsakymas: %d ir %d\n", s, t);
    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