Submission #416163

#	Time	Username	Problem	Language	Result	Execution time	Memory
416163		Kevin_Zhang_TW	Highway Tolls (IOI18_highway)	C++17	100 / 100	261 ms	19152 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;
}

pair<int,vector<int>> search_s(int f) {
	vector<int> dis(n, inf);
	dis[f] = 0;
	vector<int> q;
	q.pb(f);

	vector<vector<int>> lev(n + 1);
	for (int i = 0;i < q.size();++i) {
		int x = q[i];
		lev[ dis[x] ].pb(x);
		for (int u : edge[x]) if (u > f && chmin(dis[u], dis[x] + 1))
			q.pb(u);
	}

	int l = 0, r = (int)q.size() - 1, mid;

	reverse(AI(q));

	auto gen_vec = [&](int d) {
		vector<int> all(begin(q), begin(q)+d+1);
		for (int i = 0;i < f;++i) all.pb(i);
		return all;
	};

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

	return make_pair(q[l], lev[ edis - dis[q[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();

	auto [s, tar] = search_s(f);

	vector<int> res {s};

	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]);

		ll v = qry(l);
		int lsum = v != rdis;
		bins(l, lsum), bins(r, sum-lsum);
	};

	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;
	};

	auto vec_and = [&](vector<int> a, vector<int> b) {
		vector<int> cnt(n);
		for (int i : a) ++cnt[i];
		for (int i : b) ++cnt[i];
		vector<int> res;
		for (int i = 0;i < n;++i) if (cnt[i] == 2)
			res.pb(i);
		return res;
	};
	DE("tar", s);
	debug(AI(tar));
	bins( vec_and(get_dis(s, edis), tar), 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 'std::pair<int, std::vector<int> > search_s(int)':
highway.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (int i = 0;i < q.size();++i) {
      |                 ~~^~~~~~~~~~
highway.cpp:94:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |   mid = l + r >> 1;
      |         ~~^~~
highway.cpp: In lambda function:
highway.cpp:126:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |   if (sum == cand.size()) {
      |       ~~~~^~~~~~~~~~~~~~
highway.cpp:132:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for (int i = 0;i < cand.size();++i)
      |                  ~~^~~~~~~~~~~~~
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:165:2: note: in expansion of macro 'DE'
  165 |  DE("tar", s);
      |  ^~
highway.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
highway.cpp:166:2: note: in expansion of macro 'debug'
  166 |  debug(AI(tar));
      |  ^~~~~

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