Submission #1197134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197134		tkm_algorithms	Highway Tolls (IOI18_highway)	C++20	13 / 100	63 ms	8480 KiB

highway

/**
*    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 == 78 || i == 24 || i == 32 || i == 97 || i == 84 || i == 21 || i == 90)cost += 999;
		//} else 
			//if (i == 78 || i == 24 || i == 32 || i == 97 || i == 84 || i == 21 || i == 90)cost += 994;
	//}
	//return cost;
//}

//void answer(int x, int y) {
	//cout << x << " " << y;
	//cout << nl << cnt << nl;
//}

void find_pair(int N, vector<int> u, vector<int> v, int a, int b) {
	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 = 1, r = sza+1;
		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 << ok << " " << u[]bir << nl;
		//for ()
	}
	
	for (int i = 0; i < m; ++i)w[i] = 0;
	
	if (end == -1) {
		l = 1, r = szb+1;
		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];
	}
	
	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, 994, 999);
//}

//int32_t main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //int t = 1;
    //for (int _ = 0; _ < t; ++_) {
        //solve();
    //}
    //return 0;
//}

• Subtask 1: 0 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31