oj.uz

Submission #563140

# Submission time Handle Problem Language Result Execution time Memory
563140 2022-05-16T11:15:56 Z SeDunion Toll (BOI17_toll) C++17
0 / 100
 319 ms 186360 KB 
#include <iostream>
#include <array>
#include <cassert>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
	#include <bits/stdc++.h>
	#define cerr if(false)cerr
#endif
 
using namespace std;
using ll = long long;

const int N = 5e4 + 66;

const int K = 5;

using mat = array<array<ll, K>, K>;

mat g[N];

const ll inf = 1e18 + 123;

mat compute(mat a, mat b) {
	mat c; for (int i = 0 ; i < K ; ++ i) for (int j = 0 ; j < K ; ++ j) c[i][j] = (i == j ? 0 : inf);
	for (int i = 0 ; i < K ; ++ i) for (int j = 0 ; j < K ; ++ j) for (int k = 0 ; k < K ; ++ k) {
		c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
	}
	return c;
}

const int LOG = 18;

mat sp[N][LOG];

mat compute(int l, int r) {
	mat cur; for (int i = 0 ; i < K ; ++ i) for (int j = 0 ; j < K ; ++ j) cur[i][j] = (i == j ? 0 : inf);
	int len = r - l + 1;
	for (int i = 0 ; i < LOG ; ++ i) {
		if (len >> i & 1) {
			cur = compute(cur, sp[l][i]);
			l += 1 << i;
		}
	}
	return cur;
}

mat mid;

int qa[N], qb[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int k, n, m, q;
	cin >> k >> n >> m >> q;
	for (int b = 0 ; b < n ; ++ b) {
		for (int i = 0 ; i < k ; ++ i) {
			for (int j = 0 ; j < k ; ++ j) {
				g[b][i][j] = inf;
			}
		}
	}
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		int ba = a / k, bb = b / k;
		assert(ba + 1 == bb);
		int ia = a % k, ib = b % k;
		g[ba][ia][ib] = c;
	}
	for (int i = 0 ; i < n ; ++ i) {
		sp[i][0] = g[i];
	}
	for (int j = 1 ; j < LOG ; ++ j) {
		for (int i = 0 ; i + (1 << j) < n ; ++ i) {
			sp[i][j] = compute(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
		}
	}
	for (int i = 0 ; i < q ; ++ i) {
		cin >> qa[i] >> qb[i];
		int ba = qa[i] / k, bb = qb[i] / k;
		int ia = qa[i] % k, ib = qb[i] % k;
		ll ans;
		if (ba == bb) {
			ans = inf;
		} else if (ba == bb - 1) {
			ans = g[ba][ia][ib];
		} else {
			ans = inf;
			int l = ba + 1, r = bb - 1;
			mid = compute(l, r);
			for (int s = 0 ; s < k ; ++ s) {
				for (int t = 0 ; t < k ; ++ t) {
					ans = min(ans, mid[s][t] + g[ba][ia][s] + g[bb - 1][t][ib]);
				}
			}
		}
		if (ans >= inf) ans = -1;
		cout << ans << "\n";
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 319 ms 186316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 307 ms 186360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 319 ms 186316 KB Output isn't correct
2 Halted 0 ms 0 KB -