oj.uz

Submission #1107361

# Submission time Handle Problem Language Result Execution time Memory
1107361 2024-11-01T07:04:13 Z thieunguyenhuy Highway Tolls (IOI18_highway) C++17
18 / 100
 634 ms 59500 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, dist[2][N], e[N];
vii adj[N];
vector<int> ve[N];
map<vector<int>, ll> mem;
bitset<N> inSet;

#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(n), random(n));
		}
		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) {
		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);
			}
		}
		int ma = -1; for (auto &x : w) maximize(ma, x);
		if (ma <= 1) cerr << "kq " << dist[t] << '\n';
		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(const int type, int root) {
	memset(dist[type], -1, sizeof dist[type]); dist[type][root] = 0;
	queue<int> q; q.emplace(root);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (auto [v, id] : adj[u]) if (dist[type][v] == -1) {
			dist[type][v] = dist[type][u] + 1, e[v] = id;
			q.emplace(v);
		}
	}
}

void print(vector<int> &ve) {
	for (auto &x : ve) cerr << x << ' ';
	cerr << '\n';
}
 
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); mem.clear();
	ll fixed = myask(w); int numEdges = fixed / A;

	int low = 0, high = m - 1, edgeId = -1;
	while (low <= high) {
		int mid = low + high >> 1; vector<int> w(m, HEAVY);
		for (int i = 0; i <= mid; ++i) w[i] = LIGHT;
		if (myask(w) < 1ll * numEdges * B) high = (edgeId = mid) - 1;
		else low = mid + 1;
	}
	int u = U[edgeId], v = V[edgeId];

	cerr << "EdgeId " << edgeId << '\n';
	
	bfs(0, u), bfs(1, v); e[u] = e[v] = edgeId; vector<int> S, T;
	for (int i = 0; i < n; ++i) {
		if (dist[0][i] < dist[1][i]) S.emplace_back(i);
		else if (dist[0][i] > dist[1][i]) T.emplace_back(i);
	}

	sort (S.begin(), S.end(), [&](int x, int y) {
		return dist[0][x] < dist[0][y];
	});
	sort (T.begin(), T.end(), [&](int x, int y) {
		return dist[1][x] < dist[1][y];
	});

	cerr << "S: "; print(S);
	cerr << "T: "; print(T);

	for (auto &x : T) cerr << e[x] << ' ';
	cerr << '\n';

	auto work = [&](const int type, const vector<int> &ve) {
		vector<int> w(m, HEAVY); for (auto &x : ve) w[e[x]] = LIGHT;
		ll fixed = myask(w);

		int low = 0, high = int(ve.size()) - 2, id = ve.size() - 1;
		while (low <= high) {
			int mid = low + high >> 1; vector<int> w(m, HEAVY);
			for (int i = 0; i <= mid; ++i) w[e[ve[i]]] = LIGHT;
			// if (mid == 1) cerr << "myask = " << myask(w) << '\n';
			if (myask(w) <= fixed) high = (id = mid) - 1;
			else low = mid + 1;
		}
		return id;
	};

	int idS = work(0, S), idT = work(1, T);
	cerr << idS << ' ' << idT << '\n';
	int s = S[idS], t = T[idT];
	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; _ < 1000; ++_) {
	//     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:183:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  183 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp: In lambda function:
highway.cpp:217:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  217 |    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 5200 KB Output is correct
2 Correct 3 ms 5200 KB Output is correct
3 Correct 2 ms 5200 KB Output is correct
4 Correct 3 ms 5200 KB Output is correct
5 Correct 2 ms 5200 KB Output is correct
6 Correct 3 ms 5200 KB Output is correct
7 Correct 2 ms 5200 KB Output is correct
8 Correct 3 ms 5200 KB Output is correct
9 Correct 3 ms 5200 KB Output is correct
10 Correct 2 ms 5200 KB Output is correct
11 Correct 3 ms 5200 KB Output is correct
12 Correct 4 ms 5208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5708 KB Output is correct
2 Correct 43 ms 7376 KB Output is correct
3 Correct 400 ms 27356 KB Output is correct
4 Correct 613 ms 29792 KB Output is correct
5 Correct 633 ms 28440 KB Output is correct
6 Correct 629 ms 25236 KB Output is correct
7 Correct 605 ms 29984 KB Output is correct
8 Correct 597 ms 30076 KB Output is correct
9 Correct 355 ms 26480 KB Output is correct
10 Correct 603 ms 28452 KB Output is correct
11 Correct 484 ms 30032 KB Output is correct
12 Correct 471 ms 29708 KB Output is correct
13 Correct 631 ms 29696 KB Output is correct
14 Correct 409 ms 28920 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 7496 KB Output is correct
2 Correct 136 ms 10060 KB Output is correct
3 Correct 126 ms 12516 KB Output is correct
4 Correct 548 ms 30012 KB Output is correct
5 Correct 507 ms 30116 KB Output is correct
6 Correct 548 ms 29808 KB Output is correct
7 Correct 385 ms 28604 KB Output is correct
8 Correct 562 ms 29664 KB Output is correct
9 Correct 444 ms 29204 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5456 KB Output is correct
2 Correct 53 ms 7696 KB Output is correct
3 Correct 479 ms 22092 KB Output is correct
4 Correct 620 ms 27188 KB Output is correct
5 Correct 366 ms 26744 KB Output is correct
6 Correct 633 ms 25572 KB Output is correct
7 Correct 348 ms 26432 KB Output is correct
8 Correct 347 ms 25692 KB Output is correct
9 Correct 384 ms 30068 KB Output is correct
10 Correct 370 ms 29504 KB Output is correct
11 Correct 372 ms 28436 KB Output is correct
12 Correct 634 ms 30196 KB Output is correct
13 Correct 444 ms 29592 KB Output is correct
14 Runtime error 557 ms 59500 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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