oj.uz

Submission #1107187

# Submission time Handle Problem Language Result Execution time Memory
1107187 2024-11-01T00:11:24 Z thieunguyenhuy Highway Tolls (IOI18_highway) C++17
51 / 100
 419 ms 28168 KB 
#ifndef hwe
	#include "highway.h"
#endif
 
#include <bits/stdc++.h>
using namespace std;
 
#define popcount(n) (__builtin_popcountll((n)))
#define clz(n) (__builtin_clzll((n)))
#define ctz(n) (__builtin_ctzll((n)))
#define lg(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))
 
#define Int __int128
#define fi first
#define se second
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;
 
template <class T1, class T2>
bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2>
bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
 
template <class T>
void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T> T random(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}
 
const int N = 90000 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
 
const int LIGHT = 0, HEAVY = 1;
 
int asked = 0, maxDepth, dep[N], e[N];
vii adj[N];
vector<int> ve[N];
map<vector<int>, ll> mem;
 
#ifdef hwe
namespace Grader {
	int n, m, s, t;
	ll dist[N];
	pii edges[N];
	vii adj[N];
	vector<int> w;
 
	void get() {
		cin >> n >> m >> s >> t;
	
		for (int i = 0; i < m; ++i) {
			int u, v; cin >> u >> v;
			adj[u].emplace_back(v, i), adj[v].emplace_back(u, i);
			edges[i] = make_pair(u, v);
		}
	}
 
	void rand() {
		n = random(7, 10), m = random(n - 1, 20), s = random(n), t = random(n);
		while (s == t) t = random(n);
		for (int i = 1; i < n; ++i) {
			edges[i - 1] = make_pair(random(i), i);
		}
		for (int i = n - 1; i < m; ++i) {
			edges[i] = make_pair(random(n), random(n));
		}
		for (int i = 0; i < n; ++i) adj[i].clear();
		for (int i = 0; i < m; ++i) {
			int u, v; tie(u, v) = edges[i];
			adj[u].emplace_back(v, i), adj[v].emplace_back(u, i);
		}
	}
 
	void show() {
		cerr << n << ' ' << m << ' ' << s << ' ' << t << '\n';
		for (int i = 0; i < m; ++i) cerr << edges[i].fi << ' ' << edges[i].se << '\n';
	}
 
	ll dijkstra(int s, int t) {
		memset(dist, 0x0f, sizeof dist); dist[s] = 0;
		priority_queue<pli, vli, greater<pli>> pq; pq.emplace(0, s);
		while (!pq.empty()) {
			int u = pq.top().se; pq.pop();
			// cerr << "dijkstra " << u << ' ' << dist[u] << '\n';
			for (auto [v, id] : adj[u]) if (minimize(dist[v], dist[u] + w[id])) {
				pq.emplace(dist[v], v);
			}
		}
		int ma = -1; for (auto &x : w) maximize(ma, x);
		if (ma <= 1) cerr << "khanhquynh " << dist[t] << '\n';
		return dist[t];
	}
 
	ll ask(const vector<int> &_w) {
		w = _w; for (auto &x : w) ++x;
		return dijkstra(s, t);
	}
}
 
ll ask(const vector<int> &w) {
	return Grader::ask(w);
}
 
void answer(int s, int t) {
	cerr << "Answer " << s << ' ' << t << '\n';
}
#endif
 
ll myask(const vector<int> &w) {
	auto it = mem.find(w);
	if (it != mem.end()) return it->se;
	assert(++asked <= 50);
	return mem[w] = ask(w);
}
 
void bfs(int root) {
	memset(dep, -1, sizeof dep); dep[root] = maxDepth = 0;
	queue<int> q; q.emplace(root);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		maximize(maxDepth, dep[u]);
		for (auto [v, id] : adj[u]) if (dep[v] == -1) {
			dep[v] = dep[u] + 1;
			q.emplace(v);
		}
	}
}
 
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
	int m = U.size(); asked = 0;
	for (int i = 0; i < n; ++i) adj[i].clear();
	for (int i = 0; i < m; ++i) {
		adj[U[i]].emplace_back(V[i], i), adj[V[i]].emplace_back(U[i], i);
	}
 
	vector<int> w(m, LIGHT); mem.clear();
	ll fixed = myask(w); int numEdges = fixed / A, depthS = numEdges;
	cerr << "numEdges = " << fixed << ' ' << numEdges << '\n';
 
	bfs(random(n)); for (int i = 1; i < n; ++i) ve[i].clear();
	for (int i = 0; i < m; ++i) {
		int u = U[i], v = V[i];
		if (dep[u] == dep[v]) continue;
		if (dep[u] > dep[v]) ve[dep[u]].emplace_back(i);
		if (dep[v] > dep[u]) ve[dep[v]].emplace_back(i);
	}
	for (int i = 0; i < m; ++i) {
		int u = U[i], v = V[i];
		if (dep[u] == dep[v]) {
			ve[dep[u]].emplace_back(i);
		}
	}
 
	cerr << "depth: ";
	for (int i = 0; i < n; ++i) cerr << dep[i] << ' ';
	cerr << '\n';
 
	auto check = [&](int mid) {
		vector<int> w(m, HEAVY);
		for (int d = 1; d <= mid; ++d) for (auto id : ve[d]) {
			w[id] = LIGHT;
		}
		return myask(w) == fixed;
	};
 
	int low = 1, high = maxDepth, depthT = 0;
	while (low <= high) {
		int mid = low + high >> 1;
		if (check(mid)) high = (depthT = mid) - 1;
		else low = mid + 1;
	}
 
	// cerr << "kq ";
	// for (auto &x : ve[3]) cerr << x << ' ';
	// cerr << '\n';
	// cerr << "check = " << check(3) << '\n';
 	// cerr << "depthT = " << depthT << '\n';
 
 	assert(!ve[depthT].empty());
	low = 0, high = int(ve[depthT].size()) - 2; int posT = ve[depthT].size() - 1;
	while (low <= high) {
		int mid = low + high >> 1; vector<int> w(m, HEAVY);
		for (int i = 0; i <= mid; ++i) w[ve[depthT][i]] = LIGHT;
		if (myask(w) < 1ll * numEdges * B) high = (posT = mid) - 1;
		else low = mid + 1;
	}
	int idT = ve[depthT][posT], T = -1;
	if (dep[U[idT]] != dep[V[idT]]) T = (dep[U[idT]] > dep[V[idT]] ? U[idT] : V[idT]);
	else {
		vector<int> w(m, HEAVY); w[idT] = LIGHT; ll expected = 1ll * (numEdges - 1) * B + A;
		for (auto [v, id] : adj[U[idT]]) w[id] = LIGHT;
		T = (myask(w) < expected ? V[idT] : U[idT]);
	}
	cerr << "T = " << idT << ' ' << T << '\n';
 
	bfs(T); for (int i = 1; i < n; ++i) ve[i].clear();
	for (int i = 0; i < m; ++i) {
		int u = U[i], v = V[i];
		if (dep[u] >= dep[v]) ve[dep[u]].emplace_back(i);
		if (dep[v] >= dep[u]) ve[dep[v]].emplace_back(i);
	}
 
 	assert(!ve[depthS].empty());
	low = 0, high = int(ve[depthS].size()) - 2; int posS = ve[depthS].size() - 1;
	while (low <= high) {
		int mid = low + high >> 1; vector<int> w(m, HEAVY);
		for (int i = 0; i <= mid; ++i) w[ve[depthS][i]] = LIGHT;
		// cerr << mid << ' ' << myask(w) << '\n';
		if (myask(w) < 1ll * numEdges * B) high = (posS = mid) - 1;
		else low = mid + 1;
	}
	int idS = ve[depthS][posS], S = (dep[U[idS]] + 1 == dep[V[idS]] ? V[idS] : U[idS]);
 
	answer(S, T);
}
 
#ifdef hwe
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    #ifdef hwe
        freopen("input.inp", "r", stdin);
        freopen("output.out", "w", stdout);
    #else
        #define taskname ""
        if (fopen(taskname".inp", "r")) {
            freopen(taskname".inp", "r", stdin);
            freopen(taskname".out", "w", stdout);
        }
    #endif
 
    // for (int _ = 0; _ < 1000; ++_) {
	//     Grader::rand(); Grader::show();
	//     int n = Grader::n; vector<int> U, V;
	//     for (int i = 0; i < Grader::m; ++i) {
	//     	int u, v; tie(u, v) = Grader::edges[i];
	//     	U.emplace_back(u), V.emplace_back(v);
	//     }
	//     find_pair(n, U, V, 1, 2);    	
    // }

    Grader::get(); Grader::show();
    int n = Grader::n; vector<int> U, V;
    for (int i = 0; i < Grader::m; ++i) {
    	int u, v; tie(u, v) = Grader::edges[i];
    	U.emplace_back(u), V.emplace_back(v);
    }
    find_pair(n, U, V, 1, 2);
 
    cerr << '\n'; return 0;
}
#endif

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:205:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  205 |   int mid = low + high >> 1;
      |             ~~~~^~~~~~
highway.cpp:219:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  219 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:243:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  243 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5200 KB Output is correct
2 Correct 38 ms 6524 KB Output is correct
3 Correct 362 ms 23056 KB Output is correct
4 Correct 366 ms 22836 KB Output is correct
5 Correct 354 ms 23000 KB Output is correct
6 Correct 342 ms 21428 KB Output is correct
7 Correct 345 ms 22656 KB Output is correct
8 Correct 379 ms 21840 KB Output is correct
9 Correct 363 ms 22104 KB Output is correct
10 Correct 356 ms 21520 KB Output is correct
11 Correct 373 ms 19428 KB Output is correct
12 Correct 352 ms 18836 KB Output is correct
13 Correct 347 ms 18876 KB Output is correct
14 Correct 346 ms 17968 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6472 KB Output is correct
2 Correct 73 ms 7964 KB Output is correct
3 Correct 116 ms 9796 KB Output is correct
4 Correct 351 ms 19288 KB Output is correct
5 Correct 331 ms 19640 KB Output is correct
6 Correct 348 ms 18352 KB Output is correct
7 Correct 345 ms 19900 KB Output is correct
8 Correct 349 ms 18328 KB Output is correct
9 Correct 362 ms 19260 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5200 KB Output is correct
2 Correct 39 ms 6844 KB Output is correct
3 Correct 261 ms 16168 KB Output is correct
4 Correct 354 ms 21884 KB Output is correct
5 Correct 337 ms 20172 KB Output is correct
6 Correct 378 ms 20732 KB Output is correct
7 Correct 368 ms 19360 KB Output is correct
8 Correct 339 ms 19644 KB Output is correct
9 Correct 361 ms 22272 KB Output is correct
10 Correct 353 ms 22888 KB Output is correct
11 Correct 364 ms 19172 KB Output is correct
12 Correct 379 ms 17780 KB Output is correct
13 Correct 347 ms 18440 KB Output is correct
14 Correct 357 ms 18600 KB Output is correct
15 Correct 370 ms 17560 KB Output is correct
16 Correct 339 ms 17628 KB Output is correct
17 Correct 358 ms 19764 KB Output is correct
18 Correct 359 ms 19816 KB Output is correct
19 Correct 350 ms 19300 KB Output is correct
20 Correct 342 ms 18828 KB Output is correct
21 Correct 359 ms 24080 KB Output is correct
22 Correct 354 ms 23936 KB Output is correct
23 Correct 396 ms 26016 KB Output is correct
24 Correct 380 ms 27240 KB Output is correct
25 Correct 419 ms 28168 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6984 KB Output is correct
2 Incorrect 43 ms 6936 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 6984 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -