| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 348596 | milleniumEeee | 통행료 (IOI18_highway) | C++17 | 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.
// answer(A, B);
// ask(vector) => cost
#include "highway.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mk make_pair
#define pb push_back
#define ll long long
using namespace std;
const int MAXN = 130005;
const int INF = 0x3f3f3f3f;
int from[MAXN], to[MAXN];
vector <int> g[MAXN];
int dist[MAXN];
int pr[MAXN];
int costa, costb;
int min_path;
int diametr;
int n, m;
map <pii, int> id;
vector <pii> graph[MAXN];
int REAL_S, REAL_T;
int ask(vector <int> w) {
vector<bool> visited(n, false);
vector<long long> current_dist(n, INF);
queue<int> qa, qb;
qa.push(REAL_S);
current_dist[REAL_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 == REAL_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 + costa) {
current_dist[vv] = d + costa;
qa.push(vv);
}
} else {
if (current_dist[vv] > d + costb) {
current_dist[vv] = d + costb;
qb.push(vv);
}
}
}
}
}
}
void make_edge(int x, int y) {
g[x].pb(y);
g[y].pb(x);
}
int find_middle_edge() {
int l = 0, r = m - 1;
vector <int> w(m);
while (l != r) {
int mid = (l + r) >> 1;
for (int i = l; i <= r; i++) {
if (i <= mid) {
w[i] = 1;
} else {
w[i] = 0;
}
}
int cur_cost = ask(w);
if (cur_cost != min_path) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
int get_min_path() {
vector <int> w(m);
for (int i = 0; i < m; i++) {
w[i] = 0;
}
ll cur_cost = ask(w);
return ask(w);
}
void dfs(int v, int par, int len, vector <int> &s_sub) {
for (int to : g[v]) {
if (to != par) {
s_sub.pb(id[{v, to}]);
dfs(to, v, len + 1, s_sub);
}
}
}
void calc_dist_and_pr(int v, int par, int len) {
dist[v] = len;
pr[v] = par;
for (int to : g[v]) {
if (to != par) {
calc_dist_and_pr(to, v, len + 1);
}
}
}
int find_s(vector <int> s_sub) {
vector <int> w(m, 0);
for (int el : s_sub) {
w[el] = 1;
}
int cost = ask(w);
int root_to_s = (cost - min_path) / (costb - costa);
//cout << "4etko" << endl;
vector <int> possible;
for (int i = 0; i < n; i++) {
if (dist[i] == root_to_s) {
possible.pb(id[{i, pr[i]}]);
}
}
//cout << "possible: " << endl;
//for (int el : possible) {
//cout << el << " ";
//}cout << "\n\n";
int l = 0, r = szof(possible) - 1;
while (l != r) {
int mid = (l + r) >> 1;
for (int i = 0; i < m; i++) {
w[i] = 0;
}
for (int i = l; i <= mid; i++) {
w[possible[i]] = 1;
}
int cur_cost = ask(w);
if (cur_cost != min_path) {
r = mid;
} else {
l = mid + 1;
}
}
int need_edge = possible[l];
//cout << "need_edge: " << need_edge << endl;
if (dist[from[need_edge]] == root_to_s) {
return from[need_edge];
} else {
return to[need_edge];
}
}
void find_pair(int N, vector<int> U, vector<int> V, int AA, int BB) {
costa = AA, costb = BB;
m = U.size();
n = N;
for (int i = 0; i < m; i++) {
from[i] = U[i];
to[i] = V[i];
id[{from[i], to[i]}] = i;
id[{to[i], from[i]}] = i;
make_edge(from[i], to[i]);
graph[U[i]].push_back({V[i], i});
graph[V[i]].push_back({U[i], i});
}
min_path = get_min_path();
diametr = min_path / costa;
int mid_edge = find_middle_edge();
int root = from[mid_edge];
int need_sub = to[mid_edge];
vector <int> s_sub;
s_sub.pb(id[{root, need_sub}]);
memset(dist, -1, sizeof(dist));
calc_dist_and_pr(need_sub, root, 1);
dist[root] = 0;
dfs(need_sub, root, 1, s_sub);
//cout << "root: " << root << endl;
//cout << "need_sub: " << need_sub << endl;
//cout << "s_sub: " << endl;
//for (int el : s_sub) {
//cout << el << " ";
//}cout << "\n\n";
int SS = find_s(s_sub);
//cout << "SS: " << SS << endl;
calc_dist_and_pr(SS, -1, 0);
vector <int> possible;
for (int i = 0; i < n; i++) {
if (dist[i] == diametr) {
possible.pb(id[{i, pr[i]}]);
}
}
int l = 0, r = szof(possible) - 1;
vector <int> w(m);
while (l != r) {
int mid = (l + r) >> 1;
for (int i = 0; i < m; i++) {
w[i] = 0;
}
for (int i = l; i <= mid; i++) {
w[possible[i]] = 1;
}
int cur_cost = ask(w);
if (cur_cost != min_path) {
r = mid;
} else {
l = mid + 1;
}
}
int need_edge = possible[l];
int TT;
if (dist[from[need_edge]] == diametr) {
TT = from[need_edge];
} else {
TT = to[need_edge];
}
if (SS > TT) {
swap(SS, TT);
}
answer(SS, TT);
}
//signed main() {
//int n, m, a, b, s, t;
//cin >> n >> m >> a >> b >> s >> t;
//REAL_S = s, REAL_T = t;
//vector <int> U, V;
//U.resize(m);
//V.resize(m);
//for (int i = 0; i < m; i++) {
//cin >> U[i] >> V[i];
//}
//find_pair(n, U, V, a, b);
//}
/*
4 3 9 97 2 1
3 1
0 3
0 2
*/