oj.uz

Submission #643618

# Submission time Handle Problem Language Result Execution time Memory
643618 2022-09-22T16:03:18 Z thiago_bastos Toll (BOI17_toll) C++17
7 / 100
 64 ms 84420 KB 
#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

const int N = 5e4 + 10, K = 5, L = 16;

int adj[N][K][K], n, r, m, o, cost[L][N][K][K];

void min_path(int c[][K], int a[][K], int b[][K]) {
	int d[K][K];

	for(int i = 0; i < r; ++i)
	for(int j = 0; j < r; ++j)
		d[i][j] = INF;
	
	for(int k = 0; k < r; ++k)
		for(int i = 0; i < r; ++i)
			for(int j = 0; j < r; ++j)
				d[i][j] = min(d[i][j], a[i][k] + b[k][j]);

	for(int i = 0; i < r; ++i)
	for(int j = 0; j < r; ++j)
		c[i][j] = d[i][j];
}

void query(int a[][K], int s, int n) {
	for(int i = 0; (1 << i) <= n; ++i) {
		if(n & (1 << i)) {
			min_path(a, a, cost[i][s]);
			s += 1 << i;
		}
	}
}

void solve() {
	cin >> r >> n >> m >> o;

	n = (n - 1) / r + 1;

	for(int i = 0; i < n; ++i)
	for(int j = 0; j < r; ++j)
	for(int k = 0; k < r; ++k)
		adj[i][j][k] = INF;

	for(int i = 0; i < m; ++i) {
		int a, b, t;
		cin >> a >> b >> t;
		adj[a / r][a % r][b % r] = t;
	}

	for(int i = 0; (1 << i) < n; ++i)
	for(int j = 0; j < n; ++j)
	for(int k = 0; k < r; ++k)
	for(int l = 0; l < r; ++l)
		cost[i][j][k][l] = INF;

	for(int i = 0; i < n; ++i)
	for(int j = 0; j < r; ++j)
	for(int k = 0; k < r; ++k)
		cost[0][i][j][k] = adj[i][j][k];

	for(int i = 1; (1 << i) < n; ++i)
		for(int j = 0; j + (1 << i) <= n; ++j)
			min_path(cost[i][j], cost[i - 1][j], cost[i - 1][j + (1 << (i - 1))]);

	for(int i = 0; i < o; ++i) {
		int a, b, A[K][K];

		cin >> a >> b;

		for(int k = 0; k < r; ++k)
			for(int j = 0; j < r; ++j)
				A[k][j] = k == a % r ? adj[a / r][k][j] : INF;
		
		query(A, a / r + 1, b / r - a / r - 1);

		cout << (A[a % r][b % r] == INF ? -1 : A[a % r][b % r]) << '\n';
	}
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 83660 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 59 ms 84420 KB Output is correct
9 Correct 64 ms 84300 KB Output is correct
10 Correct 55 ms 83636 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 39624 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 83660 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 59 ms 84420 KB Output is correct
9 Correct 64 ms 84300 KB Output is correct
10 Correct 55 ms 83636 KB Output is correct
11 Correct 51 ms 39624 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Incorrect 0 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -