oj.uz

Submission #1107019

# Submission time Handle Problem Language Result Execution time Memory
1107019 2024-10-31T11:44:05 Z thieunguyenhuy Highway Tolls (IOI18_highway) C++17
51 / 100
 395 ms 17532 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];
vii adj[N];
vector<int> ve[N];
 
#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 < 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) {
		for (int i = 0; i < n; ++i) dist[i] = INF; 
		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';
	pii ans = make_pair(Grader::s, Grader::t);
	if (make_pair(s, t) != ans && make_pair(t, s) != ans) {
		cerr << "Wrong Answer\n";
		exit(0);
	}
}
#endif
 
ll myask(const vector<int> &w) {
	assert(++asked <= 50);
	return ask(w);
}

void dfs(int u, int fa) {
	maximize(maxDepth, dep[u]);
	for (auto [v, id] : adj[u]) if (dep[v] == -1) {
		dep[v] = dep[u] + 1;
		dfs(v, u);
	}
}
 
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);
	ll fixed = myask(w); int numEdges = fixed / A, depthS = numEdges;
	cerr << "numEdges = " << numEdges << '\n';

	memset(dep, -1, sizeof dep); dep[0] = 0;
	dfs(0, 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]] >= dep[V[idT]] ? U[idT] : V[idT]);
	cerr << "T = " << idT << ' ' << U[idT] << ' ' << V[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; _ < 100; ++_) {
	//     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:208:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  208 |   int mid = low + high >> 1;
      |             ~~~~^~~~~~
highway.cpp:222:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  222 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:240:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  240 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5112 KB Output is correct
5 Correct 2 ms 5112 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 5 ms 4956 KB Output is correct
2 Correct 42 ms 5712 KB Output is correct
3 Correct 340 ms 11524 KB Output is correct
4 Correct 343 ms 11576 KB Output is correct
5 Correct 340 ms 11488 KB Output is correct
6 Correct 336 ms 11404 KB Output is correct
7 Correct 341 ms 11656 KB Output is correct
8 Correct 332 ms 11676 KB Output is correct
9 Correct 374 ms 11764 KB Output is correct
10 Correct 338 ms 11516 KB Output is correct
11 Correct 358 ms 12512 KB Output is correct
12 Correct 370 ms 13148 KB Output is correct
13 Correct 345 ms 12560 KB Output is correct
14 Correct 346 ms 12444 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 6348 KB Output is correct
2 Correct 73 ms 7752 KB Output is correct
3 Correct 115 ms 9032 KB Output is correct
4 Correct 329 ms 17532 KB Output is correct
5 Correct 363 ms 17528 KB Output is correct
6 Correct 335 ms 17480 KB Output is correct
7 Correct 355 ms 17524 KB Output is correct
8 Correct 326 ms 17480 KB Output is correct
9 Correct 350 ms 17472 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4944 KB Output is correct
2 Correct 38 ms 5692 KB Output is correct
3 Correct 259 ms 10108 KB Output is correct
4 Correct 327 ms 11384 KB Output is correct
5 Correct 339 ms 11336 KB Output is correct
6 Correct 331 ms 11612 KB Output is correct
7 Correct 349 ms 11436 KB Output is correct
8 Correct 333 ms 11336 KB Output is correct
9 Correct 345 ms 11472 KB Output is correct
10 Correct 333 ms 11420 KB Output is correct
11 Correct 353 ms 12368 KB Output is correct
12 Correct 348 ms 13088 KB Output is correct
13 Correct 350 ms 12796 KB Output is correct
14 Correct 366 ms 13188 KB Output is correct
15 Correct 351 ms 11348 KB Output is correct
16 Correct 345 ms 11336 KB Output is correct
17 Correct 353 ms 12964 KB Output is correct
18 Correct 354 ms 12660 KB Output is correct
19 Correct 336 ms 11412 KB Output is correct
20 Correct 345 ms 13772 KB Output is correct
21 Correct 341 ms 11364 KB Output is correct
22 Correct 326 ms 11356 KB Output is correct
23 Correct 337 ms 11848 KB Output is correct
24 Correct 371 ms 12464 KB Output is correct
25 Correct 395 ms 16772 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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