oj.uz

답안 #1093546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1093546 2024-09-27T03:00:32 Z coldbr3w Toll (BOI17_toll) C++17
0 / 100
 299 ms 385872 KB 
	#include <bits/stdc++.h>
	using namespace std;

	#define ll long long
	#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 = 2e5 + 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];
	Matrix st[N][17];
	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;
		}
		for(int i = 0; i <= lim;i++) st[i][0] = t[i];
		for(int j = 1; j <= lim;j++){
			for(int i = 0; i + (1 << j) <= lim + 1;i++) st[i][j] = st[i][j-1] * st[i + (1 << (j - 1))][j-1]; 
		}
		while(q--){
			ll a,b; cin >> a >> b;
			if(a / k == b / k){
				cout << -1 << "\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;
			ll d = r - l + 1;
			for(int i = 16; i >= 0;i--){
				if(d & (1 << i)){
					cur = cur * st[l][i];
					l += (1 << i);
				}
			}
			for(int i = l; i <= r;i++) cur = cur * t[i];
			if(cur.d[0][b % k] > 1e17){
				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();
	}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 299 ms 385872 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 281 ms 379616 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 141352 KB Output is correct
2 Correct 60 ms 141352 KB Output is correct
3 Correct 65 ms 141248 KB Output is correct
4 Correct 59 ms 141396 KB Output is correct
5 Correct 62 ms 141312 KB Output is correct
6 Runtime error 170 ms 287604 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 141352 KB Output is correct
2 Correct 60 ms 141352 KB Output is correct
3 Correct 65 ms 141248 KB Output is correct
4 Correct 59 ms 141396 KB Output is correct
5 Correct 62 ms 141312 KB Output is correct
6 Runtime error 170 ms 287604 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 299 ms 385872 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -