Submission #744564

#	Time	Username	Problem	Language	Result	Execution time	Memory
744564		pls33	Highway Tolls (IOI18_highway)	C++17	51 / 100	207 ms	12068 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;
}

p32 find_partition(int a, int b, vvp32 &adj, vp32 &order_a, vp32 &order_b)
{
    // virsune, is kur
    queue<tuple<int, int>> q;
    q.emplace(a, 0);
    q.emplace(b, 1);

    state_t visited;
    visited[a] = true;
    visited[b] = true;

    int count_a = 0;
    int count_b = 0;
    while (!q.empty())
    {
        auto &[vertex, source] = q.front();
        q.pop();

        for (auto &[next, edge] : adj[vertex])
        {
            if (visited[next])
            {
                continue;
            }
            visited[next] = true;
            int &count = source ? count_b : count_a;
            vp32 &order = source ? order_b : order_a;

            order[count].second = next;
            order[edge].first = count++;
            q.emplace(next, source);
        }
    }

    return {count_a, count_b};
}

int find_last_edge(vp32 &order, int64_t cost, int edge_count, int count)
{
    vi32 query(edge_count);
    int low = -1, high = count - 1;

    while (low != high)
    {
        int mid = (low + 1 + high) / 2;
        for (int i = 0; i < edge_count; i++)
        {
            debug([&]()
                  {
                      if (order[i].first < mid)
                      {
                          printf("blokuoju: %d (keliai iki %d)\n", i, mid);
                      }
                      //
                  });
            query[i] = order[i].first >= mid;
        }
        debug([&]()
              {
                  putchar('\n');
                  //
              });

        int64_t new_cost = ask(query);
        debug([&]()
              {
                  printf("turiu %" PRId64 ", gavau %" PRId64 "\n", cost, new_cost);
                  //
              });
        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)
{
    A = A;
    B = B;
    const int edge_count = (int)u.size();

    vvp32 adj(n);
    for (int i = 0; i < edge_count; i++)
    {
        debug([&]()
              {
                  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];

    debug([&]()
          {
              printf("blokuoja: %d -- %d\n", a, b);
              //
          });

    vp32 order_a(edge_count, {-1, -1}), order_b(edge_count, {-1, -1});
    auto [count_a, count_b] = find_partition(a, b, adj, order_a, order_b);

    vi32 thing = {-1, -1};

    for (int i = 0; i < 2; i++)
    {
        int end = find_last_edge(order_a, cost, edge_count, count_a);
        thing[i] = (end == -1) ? a : order_a[end].second;

        swap(a, b);
        swap(order_a, order_b);
        swap(count_a, count_b);
    }
    answer(thing[0], thing[1]);
}

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