제출 #744564

#제출 시각아이디문제언어결과실행 시간메모리
744564pls33통행료 (IOI18_highway)C++17
51 / 100
207 ms12068 KiB
#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

컴파일 시 표준 에러 (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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...