oj.uz

답안 #1106936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106936 2024-10-31T09:27:17 Z thieunguyenhuy 통행료 (IOI18_highway) C++17
51 / 100
 156 ms 28228 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];
map<vector<int>, ll> mem;
 
#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) {
	auto it = mem.find(w);
	if (it != mem.end()) return it->se;
	assert(++asked <= 60);
	return mem[w] = ask(w);
}
 
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, e[v] = id;
			ve[dep[v]].emplace_back(v);
			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;
 
	for (int i = 1; i < n; ++i) ve[i].clear();
	bfs(0);
 
	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();
	bfs(T);
 
	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[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:158:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  158 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:168:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  168 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~
highway.cpp:180:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  180 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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 3 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5200 KB Output is correct
2 Correct 11 ms 6480 KB Output is correct
3 Correct 105 ms 22848 KB Output is correct
4 Correct 132 ms 22380 KB Output is correct
5 Correct 108 ms 22812 KB Output is correct
6 Correct 101 ms 21292 KB Output is correct
7 Correct 103 ms 22932 KB Output is correct
8 Correct 105 ms 21676 KB Output is correct
9 Correct 104 ms 21944 KB Output is correct
10 Correct 110 ms 22548 KB Output is correct
11 Correct 106 ms 18816 KB Output is correct
12 Correct 125 ms 18616 KB Output is correct
13 Correct 114 ms 18344 KB Output is correct
14 Correct 102 ms 18156 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 6480 KB Output is correct
2 Correct 23 ms 8224 KB Output is correct
3 Correct 31 ms 9488 KB Output is correct
4 Correct 97 ms 19716 KB Output is correct
5 Correct 112 ms 19716 KB Output is correct
6 Correct 120 ms 19396 KB Output is correct
7 Correct 107 ms 20024 KB Output is correct
8 Correct 95 ms 19444 KB Output is correct
9 Correct 106 ms 20116 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5200 KB Output is correct
2 Correct 16 ms 6736 KB Output is correct
3 Correct 84 ms 16576 KB Output is correct
4 Correct 107 ms 21440 KB Output is correct
5 Correct 99 ms 19540 KB Output is correct
6 Correct 125 ms 20760 KB Output is correct
7 Correct 99 ms 18648 KB Output is correct
8 Correct 124 ms 20504 KB Output is correct
9 Correct 106 ms 23528 KB Output is correct
10 Correct 126 ms 23448 KB Output is correct
11 Correct 123 ms 19268 KB Output is correct
12 Correct 115 ms 17872 KB Output is correct
13 Correct 117 ms 17632 KB Output is correct
14 Correct 107 ms 18320 KB Output is correct
15 Correct 120 ms 20056 KB Output is correct
16 Correct 104 ms 17904 KB Output is correct
17 Correct 116 ms 19052 KB Output is correct
18 Correct 111 ms 18664 KB Output is correct
19 Correct 113 ms 19660 KB Output is correct
20 Correct 113 ms 19140 KB Output is correct
21 Correct 130 ms 23676 KB Output is correct
22 Correct 134 ms 23780 KB Output is correct
23 Correct 121 ms 25996 KB Output is correct
24 Correct 156 ms 27188 KB Output is correct
25 Correct 138 ms 28228 KB Output is correct

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 17 ms 11856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 11848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -