Submission #415729

#	Time	Username	Problem	Language	Result	Execution time	Memory
415729		Kevin_Zhang_TW	Highway Tolls (IOI18_highway)	C++17	18 / 100	293 ms	23560 KiB

highway

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV 
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010, inf = 1e9;
#include "highway.h"

int n, m;
vector<int> edge[MAX_N];
vector<pair<int,int>> alle;
ll A, B, edis, rdis;

// node is banned
ll qry(vector<int> ban_list) {
	debug(AI(ban_list));
	vector<int> ban(n);
	for (int u : ban_list) ban[u] = true;
	vector<int> w(m);
	for (int i = 0;i < m;++i) {
		auto [x, y] = alle[i];
		w[i] = ban[x] || ban[y];
	}
	return ask(w);
}
// edge is banned

ll qry(vector<pair<int,int>> ban_list) {
	sort(AI(ban_list));
	vector<int> w(m);
	for (int i = 0;i < m;++i) {
		auto [x, y] = alle[i];
		if (binary_search(AI(ban_list), make_pair(x, y)) ||
				binary_search(AI(ban_list), make_pair(y, x)))
			w[i] = true;
	}
	return ask(w);
}

int find_on_path() {
	auto gen_vec = [&](int id) {
		vector<int> a;
		for (int i = 0;i <= id;++i) a.pb(i);
		return a;
	};
	int l = 0, r = n-1, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (qry(gen_vec(mid)) == rdis)
			l = mid+1;
		else
			r = mid;
	}
	return l;
}

vector<int> lev[MAX_N];
int search_dis(int f) {
	vector<int> dis(n, inf);
	dis[f] = 0;
	queue<int> q;
	q.emplace(f);
	while (q.size()) {
		int x = q.front(); q.pop();
		lev[ dis[x] ].pb(x);
		for (int u : edge[x]) if (chmin(dis[u], dis[x] + 1))
			q.emplace(u);
	}

	int l = 1, r = n, mid;

	auto gen_vec = [&](int d) {
		vector<int> all;
		for (int i = 0;i < n;++i) if (dis[i] < d || i <= f)
			all.pb(i);
		return all;
	};

	while (l < r) {
		mid = l + r >> 1;
		ll qv = qry(gen_vec(mid));
		if (qv == B * edis)
			r = mid;
		else
			l = mid+1;
	}

	return l;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	::A = A, ::B = B;
	n = N, m = U.size();

	for (int i = 0;i < m;++i) {
		alle.pb(U[i], V[i]);
		edge[U[i]].pb(V[i]);
		edge[V[i]].pb(U[i]);
	}

	rdis = qry( vector<int>{} );
	edis = rdis / A;

	int f = find_on_path();

	int a = search_dis(f), b = edis - a;

	vector<int> res;

	function<void(vector<int>,int)> bins = [&](vector<int> cand, int sum) {
		if (sum == 0) return;
		if (sum == cand.size()) {
			res.insert(end(res), AI(cand));
			return;
		}
		int mid = cand.size() / 2;
		vector<int> l, r;
		for (int i = 0;i < cand.size();++i)
			(i<mid?l:r).pb(cand[i]);
		DE(l.size(), r.size());

		ll v = qry(l);
		int lsum = 0, rsum = 0;
		if (sum == 2) {
			ll u = qry(r);

			if (v > rdis) lsum = 1;
			if (u > rdis) rsum = 1;

			if (v == rdis) rsum = 2;
			if (u == rdis) lsum = 2;
		}
		else {
			if (v > rdis) lsum = 1;
			else rsum = 1;
		}
		bins(l, lsum), bins(r, rsum);
	};

	DE(f, 1ll * (a + b) * A, rdis);

	DE(a);
	debug(AI(lev[a]));
	DE(b);
	debug(AI(lev[b]));

	auto get_dis = [&](int rt, int d) {
		vector<int> dis(n, inf);
		dis[rt] = 0;
		queue<int> q;
		q.emplace(rt);

		vector<int> res;
		while (q.size()) {
			int x = q.front();q.pop();
			if (dis[x] == d) res.pb(x);
			for (int u : edge[x]) if (chmin(dis[u], dis[x] + 1))
				q.emplace(u);
		}
		return res;
	};

	if (a == b) {
		bins(lev[a], 2);
	}
	else {
		assert(a > b);
		//bins(lev[a], 1);

		//bins(get_dis(res[0], edis), 1);

		bins(lev[a], 1), bins(lev[b], 1);
	}
	assert(res.size() == 2);
	answer(res[0], res[1]);
}

Compilation message (stderr)

highway.cpp: In function 'll qry(std::vector<int>)':
highway.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
highway.cpp:28:2: note: in expansion of macro 'debug'
   28 |  debug(AI(ban_list));
      |  ^~~~~
highway.cpp: In function 'int find_on_path()':
highway.cpp:60:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   mid = l + r >> 1;
      |         ~~^~~
highway.cpp: In function 'int search_dis(int)':
highway.cpp:92:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |   mid = l + r >> 1;
      |         ~~^~~
highway.cpp: In lambda function:
highway.cpp:124:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   if (sum == cand.size()) {
      |       ~~~~^~~~~~~~~~~~~~
highway.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   for (int i = 0;i < cand.size();++i)
      |                  ~~^~~~~~~~~~~~~
highway.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
highway.cpp:132:3: note: in expansion of macro 'DE'
  132 |   DE(l.size(), r.size());
      |   ^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
highway.cpp:152:2: note: in expansion of macro 'DE'
  152 |  DE(f, 1ll * (a + b) * A, rdis);
      |  ^~
highway.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
highway.cpp:154:2: note: in expansion of macro 'DE'
  154 |  DE(a);
      |  ^~
highway.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
highway.cpp:155:2: note: in expansion of macro 'debug'
  155 |  debug(AI(lev[a]));
      |  ^~~~~
highway.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
highway.cpp:156:2: note: in expansion of macro 'DE'
  156 |  DE(b);
      |  ^~
highway.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
highway.cpp:157:2: note: in expansion of macro 'debug'
  157 |  debug(AI(lev[b]));
      |  ^~~~~
highway.cpp:159:7: warning: variable 'get_dis' set but not used [-Wunused-but-set-variable]
  159 |  auto get_dis = [&](int rt, int d) {
      |       ^~~~~~~

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