oj.uz

Submission #1106990

# Submission time Handle Problem Language Result Execution time Memory
1106990 2024-10-31T11:01:27 Z thieunguyenhuy Highway Tolls (IOI18_highway) C++17
51 / 100
 178 ms 32104 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 = (dep[U[idT]] + 1 == dep[V[idT]] ? 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:226:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  226 |   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 3 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 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 2 ms 5200 KB Output is correct
2 Correct 14 ms 6588 KB Output is correct
3 Correct 117 ms 22628 KB Output is correct
4 Correct 122 ms 22156 KB Output is correct
5 Correct 125 ms 22740 KB Output is correct
6 Correct 129 ms 21444 KB Output is correct
7 Correct 123 ms 22172 KB Output is correct
8 Correct 116 ms 21728 KB Output is correct
9 Correct 102 ms 22464 KB Output is correct
10 Correct 103 ms 22620 KB Output is correct
11 Correct 110 ms 18484 KB Output is correct
12 Correct 106 ms 18360 KB Output is correct
13 Correct 100 ms 18352 KB Output is correct
14 Correct 115 ms 17892 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6480 KB Output is correct
2 Correct 20 ms 7964 KB Output is correct
3 Correct 40 ms 9540 KB Output is correct
4 Correct 95 ms 19268 KB Output is correct
5 Correct 97 ms 19456 KB Output is correct
6 Correct 98 ms 19152 KB Output is correct
7 Correct 89 ms 19616 KB Output is correct
8 Correct 99 ms 19012 KB Output is correct
9 Correct 89 ms 19664 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 12 ms 6736 KB Output is correct
3 Correct 73 ms 16148 KB Output is correct
4 Correct 116 ms 21424 KB Output is correct
5 Correct 120 ms 19504 KB Output is correct
6 Correct 99 ms 20004 KB Output is correct
7 Correct 129 ms 18812 KB Output is correct
8 Correct 101 ms 19740 KB Output is correct
9 Correct 137 ms 22572 KB Output is correct
10 Correct 119 ms 22832 KB Output is correct
11 Correct 101 ms 18776 KB Output is correct
12 Correct 108 ms 17280 KB Output is correct
13 Correct 103 ms 17240 KB Output is correct
14 Correct 108 ms 17924 KB Output is correct
15 Correct 101 ms 20200 KB Output is correct
16 Correct 115 ms 17784 KB Output is correct
17 Correct 111 ms 19092 KB Output is correct
18 Correct 110 ms 18848 KB Output is correct
19 Correct 112 ms 18820 KB Output is correct
20 Correct 104 ms 18808 KB Output is correct
21 Correct 110 ms 23536 KB Output is correct
22 Correct 116 ms 23528 KB Output is correct
23 Correct 118 ms 25660 KB Output is correct
24 Correct 128 ms 26856 KB Output is correct
25 Correct 141 ms 27992 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7016 KB Output is correct
2 Correct 19 ms 7240 KB Output is correct
3 Correct 149 ms 24832 KB Output is correct
4 Correct 145 ms 27360 KB Output is correct
5 Incorrect 178 ms 32104 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 6992 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -