oj.uz

Submission #1107010

# Submission time Handle Problem Language Result Execution time Memory
1107010 2024-10-31T11:27:52 Z thieunguyenhuy Highway Tolls (IOI18_highway) C++17
51 / 100
 376 ms 17748 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];
 
#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 < 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);
	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]] + 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

    // 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:206:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  206 |   int mid = low + high >> 1;
      |             ~~~~^~~~~~
highway.cpp:220:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  220 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:238:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  238 |   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 5 ms 4944 KB Output is correct
2 Correct 37 ms 5744 KB Output is correct
3 Correct 357 ms 11460 KB Output is correct
4 Correct 337 ms 11516 KB Output is correct
5 Correct 345 ms 11516 KB Output is correct
6 Correct 335 ms 11524 KB Output is correct
7 Correct 343 ms 11568 KB Output is correct
8 Correct 339 ms 12120 KB Output is correct
9 Correct 333 ms 11856 KB Output is correct
10 Correct 362 ms 11628 KB Output is correct
11 Correct 352 ms 12724 KB Output is correct
12 Correct 364 ms 13208 KB Output is correct
13 Correct 342 ms 12612 KB Output is correct
14 Correct 334 ms 12456 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6224 KB Output is correct
2 Correct 80 ms 7828 KB Output is correct
3 Correct 107 ms 9144 KB Output is correct
4 Correct 321 ms 17572 KB Output is correct
5 Correct 320 ms 17580 KB Output is correct
6 Correct 338 ms 17520 KB Output is correct
7 Correct 343 ms 17596 KB Output is correct
8 Correct 318 ms 17748 KB Output is correct
9 Correct 320 ms 17576 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 48 ms 5724 KB Output is correct
3 Correct 260 ms 10408 KB Output is correct
4 Correct 326 ms 11416 KB Output is correct
5 Correct 332 ms 11376 KB Output is correct
6 Correct 338 ms 11676 KB Output is correct
7 Correct 339 ms 11872 KB Output is correct
8 Correct 341 ms 11392 KB Output is correct
9 Correct 340 ms 11432 KB Output is correct
10 Correct 350 ms 11848 KB Output is correct
11 Correct 335 ms 12100 KB Output is correct
12 Correct 351 ms 13348 KB Output is correct
13 Correct 333 ms 12780 KB Output is correct
14 Correct 344 ms 13216 KB Output is correct
15 Correct 324 ms 11448 KB Output is correct
16 Correct 364 ms 11392 KB Output is correct
17 Correct 337 ms 13020 KB Output is correct
18 Correct 343 ms 12532 KB Output is correct
19 Correct 334 ms 11604 KB Output is correct
20 Correct 342 ms 13768 KB Output is correct
21 Correct 327 ms 12016 KB Output is correct
22 Correct 342 ms 11880 KB Output is correct
23 Correct 351 ms 12328 KB Output is correct
24 Correct 375 ms 12968 KB Output is correct
25 Correct 376 ms 17356 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 5960 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 43 ms 5960 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -