| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 566621 | hoanghq2004 | Highway Tolls (IOI18_highway) | C++14 | 0 ms | 0 KiB |
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>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include "highway.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
//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;
//}
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
vector <vector <pair <int, int>>> g(n), e(n);
vector <int> ord(n), id(n, -1);
int m = U.size();
for (int i = 0; i < m; ++i) {
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
// cout << U[i] << ' ' << V[i] << "asdsdfsdf\n";
}
int L = 0, R = m - 1;
vector <int> w(m, 0);
long long tot = ask(w);
while (L < R) {
int mid = L + R >> 1;
vector <int> w(m, 0);
for (int i = mid + 1; i < m; ++i) w[i] = 1;
if (ask(w) != tot) L = mid + 1;
else R = mid;
}
int x = L;
queue <int> q;
q.push(U[x]);
q.push(V[x]);
vector <int> type(n, -1);
type[U[x]] = 0;
type[V[x]] = 1;
while (q.size()) {
int u = q.front();
q.pop();
for (auto [v, i]: g[u]) {
if (type[v] != -1) continue;
type[v] = type[u];
id[v] = i;
e[u].push_back({v, i});
q.push(v);
}
}
// cout << x << '\n';
int ti = 0;
function <void(int)> dfs = [&](int u) {
ord[ti++] = u;
for (auto [v, i]: e[u]) {
dfs(v);
}
};
// cout << x << '\n';
dfs(U[x]);
// cout << U[x] << ' ' << V[x] << "aa\n";
// for (int i = 0; i < ti; ++i) cout << ord[i] << ' ';
// cout << '\n';
w.assign(m, -1);
// cout << id[0] << "aaa\n";
// for (int i = 0; i < n; ++i) cout << type[i] << ' ';
// cout << '\n';
for (int i = 0; i < n; ++i) {
if (i == U[x] || i == V[x]) continue;
w[id[i]] = 0;
}
w[x] = 0;
for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
tot = ask(w);
// cout << tot << "aafcdsfsdgf\n";
L = 0, R = ti - 1;
while (L < R) {
int mid = L + R >> 1;
vector <int> w(m, -1);
for (int i = 0; i <= mid; ++i) {
if (ord[i] == U[x] || ord[i] == V[x]) continue;
if (type[ord[i]] == 0) w[id[ord[i]]] = 0;
}
for (int i = 0; i < n; ++i) {
if (i == U[x] || i == V[x]) continue;
if (type[i] == 1) w[id[i]] = 0;
}
w[x] = 0;
for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
if (ask(w) == tot) R = mid;
else L = mid + 1;
}
int S = ord[L];
ti = 0;
dfs(V[x]);
// for (int i = 0; i < ti; ++i) cout << ord[i] << ' ';
// cout << '\n';
// for (int i = 0; i < ti; ++i) cout << ord[i] << ' ';
// cout << '\n';
L = 0, R = ti - 1;
while (L < R) {
int mid = L + R >> 1;
vector <int> w(m, -1);
for (int i = 0; i <= mid; ++i) {
if (ord[i] == U[x] || ord[i] == V[x]) continue;
if (type[ord[i]] == 1) w[id[ord[i]]] = 0;
}
for (int i = 0; i < n; ++i) {
if (i == U[x] || i == V[x]) continue;
if (type[i] == 0) w[id[i]] = 0;
}
w[x] = 0;
for (int i = 0; i < m; ++i) if (w[i] == -1) w[i] = 1;
if (ask(w) == tot) R = mid;
else L = mid + 1;
}
int T = ord[L];
// cout << S << ' ' << T << '\n';
answer(S, T);
}
/*
11 11 1 2 1 8
0 1
0 2
1 3
1 4
4 5
4 6
2 7
2 8
8 9
8 10
1 10
*/
//int main() {
//// freopen("IOI18_highway.inp", "r", stdin);
//// freopen("IOI18_highway.out", "w", stdout);
// N = read_int();
// M = read_int();
// A = read_int();
// B = read_int();
// S = read_int();
// T = read_int();
//// cout << S << ' ' << T << '\n';
//// cout << (S ^ T) << '\n';
// 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) {
//// cerr << N << ' ' << M << ' ' << A << ' ' << B << ' ' << S << ' ' << T << '\n';
//// for (int i = 0; i < M; ++i) cerr << U[i] << ' ' << V[i] << '\n';
//// assert(0);
// wrong_answer("{s, t} is wrong");
// }
// printf("Accepted: %d\n", num_calls);
// return 0;
//}