oj.uz

Submission #1106901

# Submission time Handle Problem Language Result Execution time Memory
1106901 2024-10-31T09:01:28 Z thieunguyenhuy Highway Tolls (IOI18_highway) C++17
18 / 100
 143 ms 33496 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);
		}
	}

	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) {
	assert(++asked <= 60);
	return ask(w);
}

void dfs(int u, int fa) {
	maximize(maxDepth, dep[u]);
	for (auto [v, id] : adj[u]) if (v != fa) {
		dep[v] = dep[u] + 1, e[v] = id;
		ve[dep[v]].emplace_back(v);
		dfs(v, u);
	}
}

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;

	for (int i = 1; i < n; ++i) ve[i].clear();
	dep[0] = maxDepth = 0; dfs(0, -1); 

	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 v : ve[d]) {
			w[e[v]] = LIGHT;
		}
		if (myask(w) == fixed) high = (depthT = mid) - 1;
		else low = mid + 1;
	}

	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[e[ve[depthT][i]]] = LIGHT;
		if (myask(w) < 1ll * numEdges * B) high = (posT = mid) - 1;
		else low = mid + 1;
	}
	int T = ve[depthT][posT];

	for (int i = 1; i < n; ++i) ve[i].clear();
	dep[T] = 0; dfs(T, -1); 

	low = 1, high = depthT; int depthS = 0;
	while (low <= high) {
		int mid = low + high >> 1; vector<int> w(m, HEAVY);
		for (int d = 1; d <= mid; ++d) for (auto v : ve[d]) {
			w[e[v]] = LIGHT;
		}
		if (myask(w) == fixed) high = (depthS = mid) - 1;
		else low = mid + 1;
	}

	// cerr << "depthS = " << depthS << '\n';
	// for (auto &x : ve[depthS]) cerr << x << ' ';
	// cerr << '\n';

	low = 0, high = int(ve[depthS].size()) - 1; 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[e[ve[depthS][i]]] = LIGHT;
		// cerr << mid << ' ' << myask(w) << '\n';
		if (myask(w) < 1ll * numEdges * B) high = (posS = mid) - 1;
		else low = mid + 1;
	}
	int S = ve[depthS][posS];

	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();
    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:150:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:160:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:172:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  172 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:186:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  186 |   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 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 1 ms 4688 KB Output is correct
6 Correct 2 ms 4856 KB Output is correct
7 Correct 1 ms 4688 KB Output is correct
8 Correct 1 ms 4688 KB Output is correct
9 Correct 1 ms 4688 KB Output is correct
10 Correct 2 ms 4736 KB Output is correct
11 Correct 2 ms 4688 KB Output is correct
12 Correct 2 ms 4688 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 11 ms 5200 KB Output is correct
3 Correct 126 ms 11596 KB Output is correct
4 Correct 104 ms 11620 KB Output is correct
5 Correct 106 ms 11636 KB Output is correct
6 Correct 100 ms 11688 KB Output is correct
7 Correct 99 ms 11664 KB Output is correct
8 Correct 102 ms 11836 KB Output is correct
9 Correct 93 ms 11836 KB Output is correct
10 Correct 99 ms 11732 KB Output is correct
11 Correct 103 ms 13472 KB Output is correct
12 Correct 129 ms 14916 KB Output is correct
13 Correct 123 ms 13500 KB Output is correct
14 Correct 109 ms 13976 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6480 KB Output is correct
2 Correct 26 ms 8432 KB Output is correct
3 Correct 33 ms 10304 KB Output is correct
4 Correct 100 ms 21576 KB Output is correct
5 Correct 96 ms 21580 KB Output is correct
6 Correct 103 ms 21572 KB Output is correct
7 Correct 111 ms 21584 KB Output is correct
8 Correct 98 ms 21568 KB Output is correct
9 Correct 116 ms 21568 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 14 ms 5316 KB Output is correct
3 Correct 87 ms 10172 KB Output is correct
4 Correct 123 ms 11552 KB Output is correct
5 Correct 109 ms 11424 KB Output is correct
6 Correct 99 ms 11612 KB Output is correct
7 Correct 106 ms 11636 KB Output is correct
8 Correct 94 ms 11432 KB Output is correct
9 Correct 119 ms 11536 KB Output is correct
10 Correct 110 ms 11520 KB Output is correct
11 Runtime error 143 ms 26400 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 33496 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 33488 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -