Submission #767659

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
767659	2023-06-27T02:33:56 Z	marvinthang	Highway Tolls (IOI18_highway)	C++17	100 / 100	160 ms	9876 KB

highway

/*************************************
*    author: marvinthang             *
*    created: 27.06.2023 08:31:11    *
*************************************/

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

// end of template

const long long INF = 1e18;

void find_pair(int N, vector <int> U, vector <int> V, int A, int B) {
	int M = U.size();
	int l = 0, r = M - 2;
	vector <int> w(M);
	long long len = ask(w);
	while (l <= r) {
		int m = l + r >> 1;
		fill(w.begin(), w.begin() + m + 1, 1);
		fill(m + 1 + ALL(w), 0);
		if (ask(w) > len) r = m - 1;
		else l = m + 1;
	}
	int bl = l;
	fill(ALL(w), 1);
	int s = U[bl];
	vector <vector <int>> adj(N);
	FOR(i, bl, M) {
		adj[U[i]].push_back(i);
		adj[V[i]].push_back(i);
	}
	vector <int> dist(N, -1), trace(N, -1);
	queue <int> q;
	q.push(s);
	dist[s] = 0;
	trace[s] = s;
	vector <int> ver;
	while (!q.empty()) {
		int u = q.front();
		ver.push_back(u);
		q.pop();
		for (int id: adj[u]) {
			int v = U[id] ^ V[id] ^ u;
			if (!~dist[v]) {
				dist[v] = dist[u] + 1;
				trace[v] = id;
				w[id] = 0;
				q.push(v);
			}
		}
	}
	l = 1, r = (int) ver.size() - 1;
	while (l <= r) {
		int m = l + r >> 1;
		FOR(i, m, ver.size()) w[trace[ver[i]]] = 1;
		if (ask(w) > len) l = m + 1;
		else r = m - 1;
		FOR(i, m, ver.size()) w[trace[ver[i]]] = 0;
	}
	int u = ver[r];
	int du = dist[u];
	vector <int> candidates;
	REP(v, N) if (v != u && dist[v] == len / A - du) candidates.push_back(v);
	fill(ALL(dist), -1);
	if (u != s) {
		dist[u] = 0;
		q.push(u);
		while (!q.empty()) {
			int u = q.front();
			ver.push_back(u);
			q.pop();
			for (int id: adj[u]) {
				int v = U[id] ^ V[id] ^ u;
				if (v != s && !~dist[v]) {
					dist[v] = dist[u] + 1;
					q.push(v);
				}
			}
		}
	}
	REPD(i, candidates.size()) if (~dist[candidates[i]] && dist[candidates[i]] <= len / A) {
		swap(candidates[i], candidates.back());
		candidates.pop_back();
	}
	l = 0, r = (int) candidates.size() - 2;
	while (l <= r) {
		int m = l + r >> 1;
		REP(i, m + 1) w[trace[candidates[i]]] = 1;
		if (ask(w) > len) r = m - 1;
		else l = m + 1;
		REP(i, m + 1) w[trace[candidates[i]]] = 0;
	}
	int v = candidates[l];
	answer(u, v);
}

#ifdef LOCAL
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include "highway.h"

namespace {

constexpr int MAX_NUM_CALLS = 100;
constexpr long long inffff = 1LL << 61;

int N, M, A, B, S, T;
std::vector<int> U, V;
std::vector<std::vector<std::pair<int, int>>> graph;

bool answered, wrong_pair;
int num_calls;

int read_int() {
	int x;
	if (scanf("%d", &x) != 1) {
		fprintf(stderr, "Error while reading input\n");
		exit(1);
	}
	return x;
}

void wrong_answer(const char *MSG) {
	printf("Wrong Answer: %s\n", MSG);
	exit(0);
}

}  // namespace

long long ask(const std::vector<int> &w) {
	if (++num_calls > MAX_NUM_CALLS) {
		wrong_answer("more than 100 calls to ask");
	}
	if (w.size() != (size_t)M) {
		wrong_answer("w is invalid");
	}
	for (size_t i = 0; i < w.size(); ++i) {
		if (!(w[i] == 0 || w[i] == 1)) {
			wrong_answer("w is invalid");
		}
	}

	std::vector<bool> visited(N, false);
	std::vector<long long> current_dist(N, inffff);
	std::queue<int> qa, qb;
	qa.push(S);
	current_dist[S] = 0;
	while (!qa.empty() || !qb.empty()) {
		int v;
		if (qb.empty() ||
				(!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
			v = qa.front();
			qa.pop();
		} else {
			v = qb.front();
			qb.pop();
		}
		if (visited[v]) {
			continue;
		}
		visited[v] = true;
		long long d = current_dist[v];
		if (v == T) {
			return d;
		}
		for (auto e : graph[v]) {
			int vv = e.first;
			int ei = e.second;
			if (!visited[vv]) {
				if (w[ei] == 0) {
					if (current_dist[vv] > d + A) {
						current_dist[vv] = d + A;
						qa.push(vv);
					}
				} else {
					if (current_dist[vv] > d + B) {
						current_dist[vv] = d + B;
						qb.push(vv);
					}
				}
			}
		}
	}
	return -1;
}

void answer(int s, int t) {
	if (answered) {
		wrong_answer("answered not exactly once");
	}

	if (!((s == S && t == T) || (s == T && t == S))) {
		wrong_pair = true;
	}

	answered = true;
}

int main() {
	file("highway");
	N = read_int();
	M = read_int();
	A = read_int();
	B = read_int();
	S = read_int();
	T = read_int();
	U.resize(M);
	V.resize(M);
	graph.assign(N, std::vector<std::pair<int, int>>());
	for (int i = 0; i < M; ++i) {
		U[i] = read_int();
		V[i] = read_int();
		graph[U[i]].push_back({V[i], i});
		graph[V[i]].push_back({U[i], i});
	}

	answered = false;
	wrong_pair = false;
	num_calls = 0;
	find_pair(N, U, V, A, B);
	if (!answered) {
		wrong_answer("answered not exactly once");
	}
	if (wrong_pair) {
		wrong_answer("{s, t} is wrong");
	}
	printf("Accepted: %d\n", num_calls);
	return 0;
}
#endif

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:56:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int m = l + r >> 1;
      |           ~~^~~
highway.cpp:92:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |   int m = l + r >> 1;
      |           ~~^~~
highway.cpp:125:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |   int m = l + r >> 1;
      |           ~~^~~

Subtask #1

5.0 / 5.0

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

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	6 ms	1264 KB	Output is correct
3	Correct	126 ms	8824 KB	Output is correct
4	Correct	83 ms	8876 KB	Output is correct
5	Correct	105 ms	8868 KB	Output is correct
6	Correct	112 ms	8328 KB	Output is correct
7	Correct	75 ms	8220 KB	Output is correct
8	Correct	85 ms	8864 KB	Output is correct
9	Correct	86 ms	8292 KB	Output is correct
10	Correct	126 ms	8308 KB	Output is correct
11	Correct	80 ms	7856 KB	Output is correct
12	Correct	129 ms	8764 KB	Output is correct
13	Correct	87 ms	8808 KB	Output is correct
14	Correct	103 ms	8940 KB	Output is correct

Subtask #3

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	1264 KB	Output is correct
2	Correct	20 ms	2056 KB	Output is correct
3	Correct	27 ms	1968 KB	Output is correct
4	Correct	59 ms	7148 KB	Output is correct
5	Correct	100 ms	7316 KB	Output is correct
6	Correct	104 ms	8208 KB	Output is correct
7	Correct	66 ms	5084 KB	Output is correct
8	Correct	70 ms	7512 KB	Output is correct
9	Correct	67 ms	5900 KB	Output is correct

Subtask #4

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	8 ms	1192 KB	Output is correct
3	Correct	79 ms	7236 KB	Output is correct
4	Correct	86 ms	8836 KB	Output is correct
5	Correct	56 ms	7464 KB	Output is correct
6	Correct	80 ms	7700 KB	Output is correct
7	Correct	84 ms	7944 KB	Output is correct
8	Correct	93 ms	7636 KB	Output is correct
9	Correct	100 ms	8332 KB	Output is correct
10	Correct	100 ms	8360 KB	Output is correct
11	Correct	97 ms	8748 KB	Output is correct
12	Correct	84 ms	8784 KB	Output is correct
13	Correct	101 ms	8224 KB	Output is correct
14	Correct	76 ms	7904 KB	Output is correct
15	Correct	67 ms	7540 KB	Output is correct
16	Correct	72 ms	6960 KB	Output is correct
17	Correct	104 ms	8848 KB	Output is correct
18	Correct	122 ms	8864 KB	Output is correct
19	Correct	69 ms	7460 KB	Output is correct
20	Correct	96 ms	7736 KB	Output is correct
21	Correct	83 ms	7544 KB	Output is correct
22	Correct	80 ms	6120 KB	Output is correct
23	Correct	79 ms	9552 KB	Output is correct
24	Correct	104 ms	9476 KB	Output is correct
25	Correct	97 ms	8804 KB	Output is correct

Subtask #5

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	1252 KB	Output is correct
2	Correct	14 ms	1268 KB	Output is correct
3	Correct	112 ms	9116 KB	Output is correct
4	Correct	104 ms	9128 KB	Output is correct
5	Correct	128 ms	9360 KB	Output is correct
6	Correct	113 ms	9876 KB	Output is correct
7	Correct	146 ms	9540 KB	Output is correct
8	Correct	151 ms	9644 KB	Output is correct
9	Correct	69 ms	3872 KB	Output is correct
10	Correct	137 ms	5000 KB	Output is correct
11	Correct	136 ms	6012 KB	Output is correct
12	Correct	138 ms	8920 KB	Output is correct
13	Correct	122 ms	9344 KB	Output is correct
14	Correct	136 ms	9780 KB	Output is correct
15	Correct	138 ms	9648 KB	Output is correct
16	Correct	151 ms	6848 KB	Output is correct
17	Correct	90 ms	8888 KB	Output is correct
18	Correct	81 ms	7448 KB	Output is correct
19	Correct	95 ms	9376 KB	Output is correct
20	Correct	119 ms	8168 KB	Output is correct
21	Correct	159 ms	9780 KB	Output is correct

Subtask #6

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1260 KB	Output is correct
2	Correct	13 ms	1268 KB	Output is correct
3	Correct	124 ms	9096 KB	Output is correct
4	Correct	124 ms	9236 KB	Output is correct
5	Correct	122 ms	9252 KB	Output is correct
6	Correct	156 ms	9780 KB	Output is correct
7	Correct	117 ms	9112 KB	Output is correct
8	Correct	124 ms	9204 KB	Output is correct
9	Correct	87 ms	9108 KB	Output is correct
10	Correct	144 ms	9696 KB	Output is correct
11	Correct	142 ms	9784 KB	Output is correct
12	Correct	99 ms	9656 KB	Output is correct
13	Correct	99 ms	4212 KB	Output is correct
14	Correct	132 ms	3696 KB	Output is correct
15	Correct	104 ms	6756 KB	Output is correct
16	Correct	77 ms	4900 KB	Output is correct
17	Correct	122 ms	6288 KB	Output is correct
18	Correct	78 ms	5120 KB	Output is correct
19	Correct	129 ms	8664 KB	Output is correct
20	Correct	136 ms	9360 KB	Output is correct
21	Correct	115 ms	9724 KB	Output is correct
22	Correct	103 ms	9688 KB	Output is correct
23	Correct	129 ms	9652 KB	Output is correct
24	Correct	109 ms	9832 KB	Output is correct
25	Correct	130 ms	9568 KB	Output is correct
26	Correct	160 ms	9688 KB	Output is correct
27	Correct	83 ms	8208 KB	Output is correct
28	Correct	75 ms	9144 KB	Output is correct
29	Correct	118 ms	9776 KB	Output is correct
30	Correct	95 ms	9332 KB	Output is correct
31	Correct	109 ms	9444 KB	Output is correct
32	Correct	80 ms	9224 KB	Output is correct
33	Correct	70 ms	9764 KB	Output is correct
34	Correct	115 ms	8380 KB	Output is correct
35	Correct	114 ms	8588 KB	Output is correct
36	Correct	125 ms	9292 KB	Output is correct
37	Correct	77 ms	8844 KB	Output is correct
38	Correct	76 ms	9152 KB	Output is correct
39	Correct	147 ms	9836 KB	Output is correct
40	Correct	157 ms	9800 KB	Output is correct
41	Correct	120 ms	9796 KB	Output is correct
42	Correct	146 ms	9792 KB	Output is correct