oj.uz

Submission #1106972

# Submission time Handle Problem Language Result Execution time Memory
1106972 2024-10-31T10:42:36 Z thieunguyenhuy Highway Tolls (IOI18_highway) C++17
51 / 100
 146 ms 27776 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(2, 10), m = n, 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));
		}
	}

	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 <= 60);
	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]) continue;
		if (dep[u] + 1 == dep[v]) ve[dep[v]].emplace_back(i);
		else ve[dep[u]].emplace_back(i);
	}
 
	int low = 1, high = maxDepth, depthT = 0;
	while (low <= high) {
		int mid = low + high >> 1; vector<int> w(m, HEAVY);
		for (int d = 1; d <= mid; ++d) for (auto id : ve[d]) {
			w[id] = LIGHT;
		}
		if (myask(w) == fixed) high = (depthT = mid) - 1;
		else low = mid + 1;
	}
 	cerr << "depthT = " << depthT << '\n';

	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]) continue;
		if (dep[u] + 1 == dep[v]) ve[dep[v]].emplace_back(i);
		else ve[dep[u]].emplace_back(i);
	}
 
	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:179:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  179 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:190:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  190 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:208:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  208 |   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 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 12 ms 6492 KB Output is correct
3 Correct 118 ms 22708 KB Output is correct
4 Correct 123 ms 22384 KB Output is correct
5 Correct 117 ms 22700 KB Output is correct
6 Correct 112 ms 21432 KB Output is correct
7 Correct 107 ms 22180 KB Output is correct
8 Correct 132 ms 21644 KB Output is correct
9 Correct 106 ms 22428 KB Output is correct
10 Correct 103 ms 22668 KB Output is correct
11 Correct 105 ms 18528 KB Output is correct
12 Correct 110 ms 18408 KB Output is correct
13 Correct 100 ms 18136 KB Output is correct
14 Correct 102 ms 17900 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6480 KB Output is correct
2 Correct 20 ms 7964 KB Output is correct
3 Correct 32 ms 9548 KB Output is correct
4 Correct 116 ms 19288 KB Output is correct
5 Correct 109 ms 19292 KB Output is correct
6 Correct 96 ms 19056 KB Output is correct
7 Correct 97 ms 19772 KB Output is correct
8 Correct 98 ms 19160 KB Output is correct
9 Correct 96 ms 19660 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 6700 KB Output is correct
3 Correct 76 ms 16336 KB Output is correct
4 Correct 114 ms 21188 KB Output is correct
5 Correct 105 ms 19476 KB Output is correct
6 Correct 104 ms 20004 KB Output is correct
7 Correct 101 ms 18868 KB Output is correct
8 Correct 121 ms 19688 KB Output is correct
9 Correct 122 ms 22708 KB Output is correct
10 Correct 128 ms 22968 KB Output is correct
11 Correct 108 ms 18744 KB Output is correct
12 Correct 102 ms 17392 KB Output is correct
13 Correct 113 ms 17144 KB Output is correct
14 Correct 110 ms 18112 KB Output is correct
15 Correct 105 ms 20252 KB Output is correct
16 Correct 102 ms 17796 KB Output is correct
17 Correct 118 ms 19056 KB Output is correct
18 Correct 104 ms 19156 KB Output is correct
19 Correct 102 ms 18760 KB Output is correct
20 Correct 108 ms 18840 KB Output is correct
21 Correct 129 ms 23352 KB Output is correct
22 Correct 127 ms 23504 KB Output is correct
23 Correct 145 ms 25848 KB Output is correct
24 Correct 133 ms 27016 KB Output is correct
25 Correct 146 ms 27776 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 11856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 11724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -