Submission #730992

#	Time	Username	Problem	Language	Result	Execution time	Memory
730992		pls33	Highway Tolls (IOI18_highway)	C++17	5 / 100	17 ms	752 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

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    vi32 thing((int)U.size(), 0);
    B += 0;
    int64_t initial = ask(thing);
    int64_t count = initial / A;
    int got = 0;
    vvi32 adj(N);
    for (int i = 0; i < (int)U.size(); i++)
    {
        if (count == got)
        {
            break;
        }

        thing[i]++;

        if (ask(thing) > initial)
        {
            adj[U[i]].push_back(V[i]);
            adj[V[i]].push_back(U[i]);
            got++;
        }

        thing[i]--;
    }

    vi32 result;
    for (int i = 0; i < N; i++)
    {
        if (adj[i].size() == 1)
        {
            result.push_back(i);
        }
    }

    answer(result[0], result[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");
    }

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