| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1197329 | tkm_algorithms | Highway Tolls (IOI18_highway) | C++20 | 0 ms | 0 KiB |
/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
//#include "highway.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
const char nl = '\n';
vector<int> w;
const int NN = 9e4+5;
int btreea[NN], whoma[NN];
int btreeb[NN], whomb[NN];
int cnt = 0;
//int ask(vector<int> w1) {
//cnt += 1;
//int cost = 0;
//for (int i = 0; i < sz(w1); ++i) {
//if (w1[i] == 1) {
//if (i == 29 || i == 90 || i == 94 || i == 59 || i == 96 || i == 69 || i == 83 || i == 20 || i == 8 || i == 92)cost += 3;
//} else
//if (i == 29 || i == 90 || i == 94 || i == 59 || i == 96 || i == 69 || i == 83 || i == 20 || i == 8 || i == 92)cost += 1;
//}
//return cost;
//}
//void answer(int x, int y) {
//cout << x << " " << y;
//cout << nl << cnt << nl;
//}
pair<int, int> solve(int n, vector<int> u, vector<int> v, int a, int b) {
int m = sz(u);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
function<int(int, int)> rand = [&](int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
};
function<vector<int>(vector<int>)> isolate = [&](vector<int> st) {
vector<int> c(n+1), fnd(n+1);
for (auto i: st)
c[i] = 1;
for (int i = 0; i < m; ++i) {
fnd[i] = (c[u[i]] == c[v[i]]);
}
return fnd;
};
vector<int> S, T;
while (1) {
vector<int> s1, t1;
for (int i = 0; i < n; ++i) {
if (rand(0, 1))s1.push_back(i);
else t1.push_back(i);
}
if (ask(isolate(s1))%2 ==1) {
S = s1, T = t1;
break;
}
}
while (sz(S) > 1) {
int mid = sz(S)>>1;
if (ask(isolate(S.begin(), S.begin()+mid))%2 == 1)S = vector<int>(S.begin(), S.begin()+mid);
else S = vector<int>(S.begin()+mid, S.end());
}
while (sz(T) > 1) {
int mid = sz(T)>>1;
if (ask(isolate(T.begin(), T.begin()+mid))%2 == 1)T = vector<int>(T.begin(), T.begin()+mid);
else T = vector<int>(T.begin()+mid, T.end());
}
return {S[0], T[0]};
}
void find_pair(int N, vector<int> u, vector<int> v, int a, int b) {
if (a == 1 && b == 2) {
pair<int, int> ans;
ans = solve(N, u, v, a, b);
answer(ans.first, ans.second);
return;
}
int m = sz(u), n = N;
vector<pair<int, int>> g[n+1];
w.resize(m);
for (int i = 0; i < m; ++i) {
g[u[i]].push_back({v[i], i});
g[v[i]].push_back({u[i], i});
}
ll cost = ask(w), len = cost/a;
int l = 0, r = m+1;
while (r-l>1) {
int mid = l+r>>1;
for (int i = 0; i < m; ++i) {
w[i] = 0;
if (i < mid)w[i] = 1;
}
ll d = ask(w);
if (d != cost)r = mid;
else l = mid;
}
r--;
int bir = r;
queue<pair<int, int>> q;
q.push({u[r], v[r]});
//cout << u[r] << " " << v[r] << nl;
int t = 1;
while (!q.empty()) {
int ux = q.front().first, p = q.front().second;
//cout << ux << " ";
q.pop();
for (auto i: g[ux]) {
if (i.first == p)continue;
btreea[t++] = i.second;
whoma[t-1] = i.first;
q.push({i.first, ux});
}
}
//cout << nl << t << nl;
int sza = t-1; t = 1;
q.push({v[r], u[r]});
while (!q.empty()) {
int ux = q.front().first, p = q.front().second;
q.pop();
for (auto i: g[ux]) {
if (i.first == p)continue;
btreeb[t++] = i.second;
whomb[t-1] = i.first;
q.push({i.first, ux});
}
}
int szb = t-1;
int start = -1, end = -1;
//if (sza == 1) {
//start = u[bir];
//}
//if (szb == 1)end = v[bir];
for (int i = 0; i < m; ++i)w[i] = 0;
if (start == -1) {
l = 0, r = sza+2;
bool ok = true;
while (r-l>1) {
int mid = l+r>>1;
for (int i = 1; i <= sza; ++i) {
int x = btreea[i]; w[x] = 0;
if (i >= mid)w[x] = 1;
}
ll d = ask(w);
if (d != cost) {
l = mid;
ok = false;
}
else r = mid;
}
start = whoma[l];
if (ok)start = u[bir];
//cout << start << nl;
//cout << ok << " " << u[]bir << nl;
//for ()
}
for (int i = 0; i < m; ++i)w[i] = 0;
if (end == -1) {
l = 0, r = szb+2;
bool ok = true;
while (r-l>1) {
int mid = l+r>>1;
for (int i = 1; i <= szb; ++i) {
int x = btreeb[i]; w[x] = 0;
if (i >= mid)w[x] = 1;
}
ll d = ask(w);
if (d != cost) {
l = mid;
ok = false;
}
else r = mid;
}
end = whomb[l];
if (ok)end = v[bir];
//cout << v[bir] << nl;
}
answer(start, end);
}
//void solve() {
//int n, m, s, t, a, b; cin >> n >> m >> s >> t >> a >> b;
//vector<int> u(m), v(m);
//for (int i = 0; i < m; ++i) {
//cin >> u[i] >> v[i];
//}
//find_pair(n, u, v, 1, 3);
//}
//int32_t main() {
//ios::sync_with_stdio(0);
//cin.tie(0);
//int t = 1;
//for (int _ = 0; _ < t; ++_) {
//solve();
//}
//return 0;
//}