oj.uz

Submission #1093556

# Submission time Handle Problem Language Result Execution time Memory
1093556 2024-09-27T03:18:50 Z coldbr3w Toll (BOI17_toll) C++17
0 / 100
 3000 ms 5972 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll int
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 5e4 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll k,n,m,q;
struct Matrix{
	vector<vector<ll>>d;
	ll n,m;
	void init(ll _n, ll _m){
		n = _n;
		m = _m;
		d.resize(n, vector<ll>(m));
	}
	ll col() const{
		return m;
	}
	ll row() const{
		return n;
	}
};
Matrix operator* (const Matrix &a, const Matrix &b){
	Matrix ans;
	ans.init(a.row(), b.col());
	for(int i = 0; i < a.row();i++){
		for(int j = 0; j < b.col();j++) ans.d[i][j] = inf;
	}
	for(int i = 0; i < a.row(); i++){
		for(int j = 0; j < b.col();j++){
			for(int k = 0; k < a.col();k++){
				ans.d[i][j] = min(ans.d[i][j], a.d[i][k] + b.d[k][j]);
			}
		}
	}
	return ans;
}
Matrix t[N];
void to_thic_cau(){
	cin >> k >> n >> m >> q;
	ll lim = (n - 1) / k;
	for(int i = 0; i <= lim;i++){
		t[i].init(k, k);
		for(int j = 0; j < k;j++){
			for(int x = 0; x < k;x++) t[i].d[j][x] = inf;
		}
	}
	for(int i = 1; i <= m;i++){
		ll u,v,w; cin >> u >> v >> w;
		t[v / k].d[u % k][v % k] = w;
	}
	while(q--){
		ll a,b; cin >> a >> b;
		if(a / k == b / k){
			if(a != b) cout << -1 << "\n";
			else if(a == b) cout << 0 << "\n";
			continue;
		}
		ll l = a / k + 1, r = b / k;
		Matrix cur; 
		cur.init(1, k);
		for(int i = 0; i < k;i++) cur.d[0][i] = inf;
		cur.d[0][a % k] = 0;
		for(int i = l; i <= r;i++) cur = cur * t[i];
		if(cur.d[0][b % k] >= 1e9){
			cout << -1 << "\n";
		}
		else cout << cur.d[0][b % k] << "\n";
	}
}   

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Compilation message

toll.cpp:12:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 | const ll inf = 1e18;
      |                ^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 ms 5908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 5972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 ms 5908 KB Time limit exceeded
2 Halted 0 ms 0 KB -