oj.uz

Submission #1107404

# Submission time Handle Problem Language Result Execution time Memory
1107404 2024-11-01T07:42:21 Z thieunguyenhuy Highway Tolls (IOI18_highway) C++17
18 / 100
 416 ms 60060 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[2][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 < n; ++i) adj[i].clear();

		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, 7), m = random(n - 1, 15), 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';
	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) {
	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[type][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, LIGHT);
		for (int i = 0; i <= mid; ++i) w[i] = HEAVY;
		if (myask(w) > 1ll * numEdges * A) high = (edgeId = mid) - 1;
		else low = mid + 1;
	}
	int u = U[edgeId], v = V[edgeId];

	cerr << "EdgeId " << edgeId << '\n';
	
	memset(e, -1, sizeof e);
	bfs(0, u), bfs(1, v); e[0][u] = e[1][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 : S) cerr << e[x] << ' ';
	// cerr << '\n';
	// 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) assert(e[type][x] != -1), w[e[type][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[type][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:190:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  190 |   int mid = low + high >> 1; vector<int> w(m, LIGHT);
      |             ~~~~^~~~~~
highway.cpp: In lambda function:
highway.cpp:227:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  227 |    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 5968 KB Output is correct
2 Correct 3 ms 5968 KB Output is correct
3 Correct 2 ms 5968 KB Output is correct
4 Correct 3 ms 5968 KB Output is correct
5 Correct 3 ms 5968 KB Output is correct
6 Correct 3 ms 5968 KB Output is correct
7 Correct 3 ms 5968 KB Output is correct
8 Correct 4 ms 5968 KB Output is correct
9 Correct 3 ms 5968 KB Output is correct
10 Correct 2 ms 5968 KB Output is correct
11 Correct 3 ms 5968 KB Output is correct
12 Correct 3 ms 5968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6224 KB Output is correct
2 Correct 42 ms 8160 KB Output is correct
3 Correct 359 ms 27564 KB Output is correct
4 Correct 366 ms 29468 KB Output is correct
5 Correct 369 ms 28292 KB Output is correct
6 Correct 368 ms 24984 KB Output is correct
7 Correct 372 ms 29812 KB Output is correct
8 Correct 395 ms 29584 KB Output is correct
9 Correct 364 ms 26672 KB Output is correct
10 Correct 358 ms 28200 KB Output is correct
11 Correct 368 ms 30080 KB Output is correct
12 Correct 367 ms 30116 KB Output is correct
13 Correct 365 ms 29280 KB Output is correct
14 Correct 385 ms 29132 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8100 KB Output is correct
2 Correct 91 ms 10688 KB Output is correct
3 Correct 122 ms 12980 KB Output is correct
4 Correct 369 ms 30144 KB Output is correct
5 Correct 357 ms 29996 KB Output is correct
6 Correct 364 ms 29772 KB Output is correct
7 Correct 397 ms 29180 KB Output is correct
8 Correct 387 ms 29804 KB Output is correct
9 Correct 386 ms 29232 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6224 KB Output is correct
2 Correct 41 ms 8352 KB Output is correct
3 Correct 278 ms 22184 KB Output is correct
4 Correct 376 ms 27220 KB Output is correct
5 Correct 378 ms 27228 KB Output is correct
6 Correct 356 ms 25560 KB Output is correct
7 Correct 368 ms 26732 KB Output is correct
8 Correct 373 ms 26004 KB Output is correct
9 Correct 372 ms 30616 KB Output is correct
10 Correct 390 ms 29924 KB Output is correct
11 Correct 389 ms 28728 KB Output is correct
12 Correct 416 ms 30108 KB Output is correct
13 Correct 377 ms 29604 KB Output is correct
14 Runtime error 411 ms 60060 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 42 ms 8520 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 40 ms 8520 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -