oj.uz

Submission #1107027

# Submission time Handle Problem Language Result Execution time Memory
1107027 2024-10-31T11:58:20 Z thieunguyenhuy Highway Tolls (IOI18_highway) C++17
51 / 100
 179 ms 32112 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(i), random(i));
		}
		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);
			}
		}
		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 < m; ++i) {
		adj[U[i]].emplace_back(V[i], i), adj[V[i]].emplace_back(U[i], i);
	}
 
	vector<int> w(m, LIGHT);
	ll fixed = myask(w); int numEdges = fixed / A, depthS = numEdges;
	cerr << "numEdges = " << numEdges << '\n';
 
	bfs(0); 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);
	}
 
	// 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 = " << 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
 
    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:194:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  194 |   int mid = low + high >> 1;
      |             ~~~~^~~~~~
highway.cpp:208:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  208 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:232:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  232 |   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 5116 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 2 ms 4944 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 3 ms 5172 KB Output is correct
2 Correct 13 ms 6480 KB Output is correct
3 Correct 114 ms 22564 KB Output is correct
4 Correct 121 ms 22264 KB Output is correct
5 Correct 131 ms 22592 KB Output is correct
6 Correct 120 ms 21488 KB Output is correct
7 Correct 106 ms 22172 KB Output is correct
8 Correct 119 ms 21716 KB Output is correct
9 Correct 115 ms 22392 KB Output is correct
10 Correct 114 ms 22696 KB Output is correct
11 Correct 126 ms 18548 KB Output is correct
12 Correct 125 ms 18356 KB Output is correct
13 Correct 105 ms 18308 KB Output is correct
14 Correct 102 ms 17932 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6352 KB Output is correct
2 Correct 21 ms 8212 KB Output is correct
3 Correct 35 ms 9552 KB Output is correct
4 Correct 95 ms 19504 KB Output is correct
5 Correct 92 ms 19384 KB Output is correct
6 Correct 101 ms 19100 KB Output is correct
7 Correct 98 ms 19644 KB Output is correct
8 Correct 92 ms 19004 KB Output is correct
9 Correct 95 ms 19640 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5200 KB Output is correct
2 Correct 16 ms 6668 KB Output is correct
3 Correct 77 ms 16156 KB Output is correct
4 Correct 109 ms 21224 KB Output is correct
5 Correct 97 ms 19488 KB Output is correct
6 Correct 107 ms 20324 KB Output is correct
7 Correct 99 ms 18836 KB Output is correct
8 Correct 96 ms 19824 KB Output is correct
9 Correct 117 ms 22704 KB Output is correct
10 Correct 131 ms 23056 KB Output is correct
11 Correct 108 ms 18836 KB Output is correct
12 Correct 105 ms 17388 KB Output is correct
13 Correct 100 ms 17144 KB Output is correct
14 Correct 108 ms 18056 KB Output is correct
15 Correct 116 ms 20224 KB Output is correct
16 Correct 101 ms 17804 KB Output is correct
17 Correct 107 ms 19060 KB Output is correct
18 Correct 110 ms 18992 KB Output is correct
19 Correct 110 ms 18776 KB Output is correct
20 Correct 104 ms 18808 KB Output is correct
21 Correct 111 ms 23460 KB Output is correct
22 Correct 115 ms 23488 KB Output is correct
23 Correct 126 ms 25708 KB Output is correct
24 Correct 131 ms 26808 KB Output is correct
25 Correct 142 ms 27880 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6992 KB Output is correct
2 Correct 15 ms 7248 KB Output is correct
3 Correct 134 ms 24944 KB Output is correct
4 Correct 140 ms 27440 KB Output is correct
5 Incorrect 179 ms 32112 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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