oj.uz

Submission #1106857

# Submission time Handle Problem Language Result Execution time Memory
1106857 2024-10-31T08:03:52 Z thieunguyenhuy Highway Tolls (IOI18_highway) C++17
12 / 100
 127 ms 33344 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 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

void dfs(int u, int fa) {
	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();
	for (int i = 0; i < m; ++i) {
		adj[U[i]].emplace_back(V[i], i), adj[V[i]].emplace_back(U[i], i);
	}

	dfs(0, -1);

	int low = 1, high = n - 1, depth = 0;
	while (low <= high) {
		int mid = low + high >> 1; vector<int> w(m, HEAVY); ll expected = 1ll * mid * A;
		for (int d = 1; d <= mid; ++d) for (auto v : ve[d]) {
			w[e[v]] = LIGHT;
		}
		// cerr << mid << ' ' << ask(w) << '\n';
		if (expected <= ask(w)) low = (depth = mid) + 1;
		else high = mid - 1;
	}

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

	low = 0, high = ve[depth].size() - 1; int pos = -1; ll expected = 1ll * depth * B;
	while (low <= high) {
		int mid = low + high >> 1; vector<int> w(m, HEAVY);
		for (int i = 0; i <= mid; ++i) w[e[ve[depth][i]]] = LIGHT;
		// cerr << mid << ' ' << ask(w) << '\n';
		if (ask(w) < expected) high = (pos = mid) - 1;
		else low = mid + 1;
	}

	answer(0, ve[depth][pos]);
}

#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:140:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  140 |   int mid = low + high >> 1; vector<int> w(m, HEAVY); ll expected = 1ll * mid * A;
      |             ~~~~^~~~~~
highway.cpp:155:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  155 |   int mid = low + high >> 1; vector<int> w(m, HEAVY);
      |             ~~~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 4688 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 2 ms 4688 KB Output is correct
8 Correct 1 ms 4688 KB Output is correct
9 Correct 2 ms 4688 KB Output is correct
10 Correct 2 ms 4688 KB Output is correct
11 Correct 3 ms 4688 KB Output is correct
12 Correct 1 ms 4688 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4688 KB Output is correct
2 Correct 14 ms 5200 KB Output is correct
3 Correct 127 ms 11084 KB Output is correct
4 Correct 123 ms 11648 KB Output is correct
5 Correct 121 ms 11096 KB Output is correct
6 Correct 109 ms 11028 KB Output is correct
7 Correct 125 ms 11084 KB Output is correct
8 Correct 123 ms 11176 KB Output is correct
9 Correct 94 ms 11096 KB Output is correct
10 Correct 122 ms 11096 KB Output is correct
11 Correct 105 ms 12872 KB Output is correct
12 Correct 97 ms 14132 KB Output is correct
13 Correct 95 ms 13152 KB Output is correct
14 Correct 94 ms 12164 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 6348 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4688 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 33328 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 60 ms 33344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -