oj.uz

Submission #416163

# Submission time Handle Problem Language Result Execution time Memory
416163 2021-06-02T06:04:04 Z Kevin_Zhang_TW Highway Tolls (IOI18_highway) C++17
100 / 100
 261 ms 19152 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7240 KB Output is correct
2 Correct 5 ms 7240 KB Output is correct
3 Correct 5 ms 7240 KB Output is correct
4 Correct 5 ms 7240 KB Output is correct
5 Correct 5 ms 7352 KB Output is correct
6 Correct 5 ms 7240 KB Output is correct
7 Correct 5 ms 7240 KB Output is correct
8 Correct 8 ms 7240 KB Output is correct
9 Correct 5 ms 7240 KB Output is correct
10 Correct 5 ms 7240 KB Output is correct
11 Correct 5 ms 7240 KB Output is correct
12 Correct 5 ms 7240 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7368 KB Output is correct
2 Correct 19 ms 8308 KB Output is correct
3 Correct 172 ms 16896 KB Output is correct
4 Correct 163 ms 16796 KB Output is correct
5 Correct 173 ms 16844 KB Output is correct
6 Correct 163 ms 16788 KB Output is correct
7 Correct 182 ms 16924 KB Output is correct
8 Correct 174 ms 16984 KB Output is correct
9 Correct 158 ms 17008 KB Output is correct
10 Correct 163 ms 16820 KB Output is correct
11 Correct 188 ms 16896 KB Output is correct
12 Correct 180 ms 17324 KB Output is correct
13 Correct 168 ms 17024 KB Output is correct
14 Correct 166 ms 16748 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8668 KB Output is correct
2 Correct 31 ms 9848 KB Output is correct
3 Correct 46 ms 10392 KB Output is correct
4 Correct 126 ms 17936 KB Output is correct
5 Correct 127 ms 18052 KB Output is correct
6 Correct 122 ms 18444 KB Output is correct
7 Correct 128 ms 16536 KB Output is correct
8 Correct 127 ms 18172 KB Output is correct
9 Correct 130 ms 17052 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7368 KB Output is correct
2 Correct 21 ms 8532 KB Output is correct
3 Correct 133 ms 14760 KB Output is correct
4 Correct 181 ms 16132 KB Output is correct
5 Correct 164 ms 16696 KB Output is correct
6 Correct 152 ms 15964 KB Output is correct
7 Correct 162 ms 16528 KB Output is correct
8 Correct 180 ms 16164 KB Output is correct
9 Correct 173 ms 16808 KB Output is correct
10 Correct 166 ms 17084 KB Output is correct
11 Correct 154 ms 16088 KB Output is correct
12 Correct 166 ms 16876 KB Output is correct
13 Correct 172 ms 16772 KB Output is correct
14 Correct 188 ms 16908 KB Output is correct
15 Correct 160 ms 16788 KB Output is correct
16 Correct 167 ms 16140 KB Output is correct
17 Correct 168 ms 16556 KB Output is correct
18 Correct 152 ms 16104 KB Output is correct
19 Correct 142 ms 16008 KB Output is correct
20 Correct 138 ms 15808 KB Output is correct
21 Correct 162 ms 16980 KB Output is correct
22 Correct 160 ms 17100 KB Output is correct
23 Correct 146 ms 17424 KB Output is correct
24 Correct 189 ms 17320 KB Output is correct
25 Correct 193 ms 18468 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8464 KB Output is correct
2 Correct 24 ms 8516 KB Output is correct
3 Correct 183 ms 17668 KB Output is correct
4 Correct 205 ms 18112 KB Output is correct
5 Correct 234 ms 18964 KB Output is correct
6 Correct 242 ms 18700 KB Output is correct
7 Correct 249 ms 18384 KB Output is correct
8 Correct 228 ms 19152 KB Output is correct
9 Correct 186 ms 13888 KB Output is correct
10 Correct 178 ms 14188 KB Output is correct
11 Correct 172 ms 14604 KB Output is correct
12 Correct 212 ms 17124 KB Output is correct
13 Correct 232 ms 18076 KB Output is correct
14 Correct 230 ms 18908 KB Output is correct
15 Correct 238 ms 18988 KB Output is correct
16 Correct 195 ms 15360 KB Output is correct
17 Correct 158 ms 17520 KB Output is correct
18 Correct 170 ms 17004 KB Output is correct
19 Correct 153 ms 17476 KB Output is correct
20 Correct 169 ms 17156 KB Output is correct
21 Correct 235 ms 18904 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8512 KB Output is correct
2 Correct 23 ms 8432 KB Output is correct
3 Correct 194 ms 17768 KB Output is correct
4 Correct 204 ms 17976 KB Output is correct
5 Correct 209 ms 17580 KB Output is correct
6 Correct 233 ms 19116 KB Output is correct
7 Correct 184 ms 17788 KB Output is correct
8 Correct 192 ms 17952 KB Output is correct
9 Correct 194 ms 18192 KB Output is correct
10 Correct 224 ms 18960 KB Output is correct
11 Correct 238 ms 18584 KB Output is correct
12 Correct 250 ms 18644 KB Output is correct
13 Correct 197 ms 14812 KB Output is correct
14 Correct 187 ms 14136 KB Output is correct
15 Correct 195 ms 15044 KB Output is correct
16 Correct 183 ms 14336 KB Output is correct
17 Correct 188 ms 14816 KB Output is correct
18 Correct 177 ms 14268 KB Output is correct
19 Correct 218 ms 17212 KB Output is correct
20 Correct 220 ms 18332 KB Output is correct
21 Correct 230 ms 18820 KB Output is correct
22 Correct 235 ms 18728 KB Output is correct
23 Correct 239 ms 18796 KB Output is correct
24 Correct 243 ms 18820 KB Output is correct
25 Correct 245 ms 18040 KB Output is correct
26 Correct 261 ms 18840 KB Output is correct
27 Correct 172 ms 17084 KB Output is correct
28 Correct 152 ms 16848 KB Output is correct
29 Correct 166 ms 17084 KB Output is correct
30 Correct 177 ms 16900 KB Output is correct
31 Correct 202 ms 17084 KB Output is correct
32 Correct 165 ms 16868 KB Output is correct
33 Correct 202 ms 17076 KB Output is correct
34 Correct 151 ms 17456 KB Output is correct
35 Correct 170 ms 17996 KB Output is correct
36 Correct 177 ms 16952 KB Output is correct
37 Correct 170 ms 17104 KB Output is correct
38 Correct 192 ms 17104 KB Output is correct
39 Correct 236 ms 18912 KB Output is correct
40 Correct 231 ms 19068 KB Output is correct
41 Correct 222 ms 18140 KB Output is correct
42 Correct 227 ms 18916 KB Output is correct