This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
distance[start] = 0;
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 < mid; 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;
}
int l = -1, r = -1;
for (int i = 0; i < 2; i++)
{
vp32 order;
vi32 distance(n, INT_MAX);
find_bfs_order(a, b, adj, order, distance);
if (!order.size())
{
l = a;
swap(l, r);
swap(a, b);
continue;
}
int end = find_end_edge(order, (cost / A) * B, edge_count);
l = (end == -1) ? a : order[end].second;
swap(l, r);
swap(a, b);
}
answer(l, r);
}
#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
|
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |