Submission #767675

#	Time	Username	Problem	Language	Result	Execution time	Memory
767675		marvinthang	Highway Tolls (IOI18_highway)	C++17	13 / 100	175 ms	18372 KiB

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;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
template <class T> T rand(T l, T h) { return uniform_int_distribution <T> (l, h) (rng); } 
template <class T> T rand(T h) { return uniform_int_distribution <T> (0, h - 1) (rng); } 

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);
	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(U[bl]);
	dist[U[bl]] = 0;
	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);
			}
		}
	}
	REP(i, N) adj[i].clear();
	REP(u, N) {
		int id = trace[u];
		if (!~id) continue;
		int v = U[id] ^ V[id] ^ u;
		if (v == U[bl]) continue;
		adj[u].push_back(id);
		adj[v].push_back(id);
	}
	vector <bool> visited(N);
	q.push(V[bl]);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int id: adj[u]) {
			int v = U[id] ^ V[id] ^ u;
			if (!visited[v]) {
				visited[v] = true;
				q.push(v);
			}
		}
	}
	vector <int> left, right;
	for (int u: ver) (visited[u] ? right : left).push_back(u);
	l = 1, r = (int) left.size() - 1;
	while (l <= r) {
		int m = l + r >> 1;
		FOR(i, m, left.size()) w[trace[left[i]]] = 1;
		if (ask(w) > len) l = m + 1;
		else r = m - 1;
		FOR(i, m, left.size()) w[trace[left[i]]] = 0;
	}
	int s = left[r];
	l = 1, r = (int) right.size() - 1;
	while (l <= r) {
		int m = l + r >> 1;
		FOR(i, m, right.size()) w[trace[right[i]]] = 1;
		if (ask(w) > len) l = m + 1;
		else r = m - 1;
		FOR(i, m, right.size()) w[trace[right[i]]] = 0;
	}
	int t = right[r];
	answer(s, t);
}

#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 (stderr)

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

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