oj.uz

Submission #304638

# Submission time Handle Problem Language Result Execution time Memory
304638 2020-09-21T16:15:02 Z Falcon Toll (BOI17_toll) C++17
46 / 100
 3000 ms 46016 KB 
#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
	#include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
	#define debug(x...) { dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals); }
	#define light_debug(x) { dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0; }
#else
	#define debug(x...)
	#define light_debug(x) 
#endif

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

constexpr int MAXN{50'000};
constexpr ll INF{1LL << 40};

int K, N, M, O;
vector<vector<pii>> adj;
ll dist[MAXN][20][5]{}; //dist[a][b][c] = distance between [a] and [K * (a/K + 2^b) + c]

void precalc() {
	int max_k = __lg((N + K - 1) / K);
	rep(i, N) 
		rep(j, 1 + max_k)
			rep(k, K)
				dist[i][j][k] = INF;
	rep(v, N)
		for(auto u : adj[v])
			dist[v][0][u.first % K] = u.second;

	rep1(k, max_k)
		rep(v, N)
			rep(x, K) 
				rep(y, K) {
					int u = K * (v / K + (1 << (k - 1))) + y;
					if(u >= N) continue;
					ckmin(dist[v][k][x], dist[v][k - 1][y] + dist[u][k - 1][x]);
				}
}

ll query(int a, int b) { 
	if(a == b)
		return 0;
	else if(a / K >= b / K)
		return INF;
	int d = __lg(b / K - a / K);
	ll ans = INF;
	rep(i, K) {
		int u = K * (a / K + (1 << d)) + i;
		if(u >= N) continue;
		ckmin(ans, dist[a][d][i] + query(u, b));
	}
	return ans;
}


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	#ifdef DEBUG
		freopen("debug", "w", stderr);
	#endif
	
	cin >> K >> N >> M >> O;
	adj.resize(N);

	rep(_, M) {
		int a, b, t; cin >> a >> b >> t;
		adj[a].pb({b, t});
	}

	precalc();

	rep(_, O) {
		int a, b; cin >> a >> b;
		ll d = query(a, b);
		if(d < INF)
			cout << d << '\n';
		else
			cout << -1 << '\n';
	}


	#ifdef DEBUG
		dbg::dout << "\nExecution time: " << clock() << "ms\n";
	#endif

	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 42360 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 2 ms 1152 KB Output is correct
7 Correct 2 ms 1152 KB Output is correct
8 Correct 63 ms 43128 KB Output is correct
9 Correct 61 ms 43000 KB Output is correct
10 Correct 41 ms 40824 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 42488 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 5 ms 1408 KB Output is correct
8 Correct 12 ms 1408 KB Output is correct
9 Correct 64 ms 43128 KB Output is correct
10 Execution timed out 3069 ms 45672 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 2 ms 1152 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 3 ms 1152 KB Output is correct
10 Correct 56 ms 42232 KB Output is correct
11 Correct 102 ms 43768 KB Output is correct
12 Correct 145 ms 45308 KB Output is correct
13 Correct 171 ms 45868 KB Output is correct
14 Correct 148 ms 44536 KB Output is correct
15 Correct 466 ms 27000 KB Output is correct
16 Correct 1144 ms 27000 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 2 ms 1152 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 3 ms 1152 KB Output is correct
10 Correct 56 ms 42232 KB Output is correct
11 Correct 102 ms 43768 KB Output is correct
12 Correct 145 ms 45308 KB Output is correct
13 Correct 171 ms 45868 KB Output is correct
14 Correct 148 ms 44536 KB Output is correct
15 Correct 466 ms 27000 KB Output is correct
16 Correct 1144 ms 27000 KB Output is correct
17 Correct 141 ms 43860 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 1280 KB Output is correct
24 Correct 5 ms 1280 KB Output is correct
25 Correct 63 ms 1280 KB Output is correct
26 Correct 31 ms 1280 KB Output is correct
27 Correct 66 ms 43128 KB Output is correct
28 Correct 646 ms 45468 KB Output is correct
29 Correct 596 ms 46016 KB Output is correct
30 Correct 661 ms 44756 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 42360 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 2 ms 1152 KB Output is correct
7 Correct 2 ms 1152 KB Output is correct
8 Correct 63 ms 43128 KB Output is correct
9 Correct 61 ms 43000 KB Output is correct
10 Correct 41 ms 40824 KB Output is correct
11 Correct 201 ms 42488 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 5 ms 1408 KB Output is correct
18 Correct 12 ms 1408 KB Output is correct
19 Correct 64 ms 43128 KB Output is correct
20 Execution timed out 3069 ms 45672 KB Time limit exceeded
21 Halted 0 ms 0 KB -