oj.uz

Submission #696813

# Submission time Handle Problem Language Result Execution time Memory
696813 2023-02-07T10:28:05 Z nhphan0505 Toll (BOI17_toll) C++17
100 / 100
 1061 ms 389628 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define gcd __gcd
#define endl '\n'
const int N=200050,M=1000000007;
const ll INF=1e18;

struct matrix{
	ll n, m;
	vector<vector<ll>> a;
	
	matrix(ll x, ll y, ll v=0){
		n=x, m=y;
		a.assign(n, vector<ll>(m, v));
	}
	
	auto & operator [](ll i){return a[i];}
	const auto & operator [](ll i)const{return a[i];}
	
	matrix()=default;
	
	friend ostream& operator <<(ostream& stream, const matrix &x){
		for(auto i:x.a){
			for(auto j:i) stream<<j<<" ";
			stream<<endl;
		}
		return stream;
	}
	
	matrix operator *(const matrix b){
		matrix a=*this, res(a.n, b.m, INF);
		// cout<<b<<a;
		for(ll i=0; i<a.n; i++)
			for(ll j=0; j<b.m; j++)
				for(ll k=0; k<a.m; k++)
					res[i][j]=min(res[i][j], a[i][k]+b[k][j]);
		// cout<<res<<"\n";
		return res;
	}
};

matrix p[N][17];
ll k, n, m, q, a, b, t;

signed main(){
	ios_base::sync_with_stdio(NULL); 
	cin.tie(nullptr); cout.tie(nullptr);
	cin>>k>>n>>m>>q;
	for(ll i=0; i<n; i++)
		for(ll j=0; j<17; j++)  p[i][j]=matrix(k, k, INF);
		
	while(m--){
		cin>>a>>b>>t;
		p[a/k][0][a%k][b%k]=t;
	}
	for(ll i=1; (1<<i)<=n; i++)
		for(ll j=0; j+(1<<i)-1<=n; j++){
			p[j][i]=p[j][i-1]*p[j+(1<<(i-1))][i-1];
		}
	while(q--){
		cin>>a>>b;
		if(a == b){
    		cout<<0<<endl;
    		continue;
    	}
		ll now=a/k, l=b/k-a/k;
		matrix res(k, k, INF);
		for(ll i=0; i<k; i++) res[i][i]=0;
		for(ll i=0; i<17; i++)
			if(l&(1<<i)){
				res=res*p[now][i];
				now+=(1<<i);
			}
		cout<<(res[a%k][b%k]==INF? -1: res[a%k][b%k])<<endl;
	}
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 186704 KB Output is correct
2 Correct 62 ms 133488 KB Output is correct
3 Correct 61 ms 133400 KB Output is correct
4 Correct 60 ms 133328 KB Output is correct
5 Correct 68 ms 134384 KB Output is correct
6 Correct 74 ms 134408 KB Output is correct
7 Correct 67 ms 134440 KB Output is correct
8 Correct 408 ms 187496 KB Output is correct
9 Correct 415 ms 187492 KB Output is correct
10 Correct 382 ms 186776 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 239932 KB Output is correct
2 Correct 62 ms 133332 KB Output is correct
3 Correct 61 ms 133408 KB Output is correct
4 Correct 64 ms 133468 KB Output is correct
5 Correct 61 ms 133460 KB Output is correct
6 Correct 61 ms 133476 KB Output is correct
7 Correct 78 ms 134512 KB Output is correct
8 Correct 90 ms 135600 KB Output is correct
9 Correct 395 ms 187548 KB Output is correct
10 Correct 786 ms 282048 KB Output is correct
11 Correct 575 ms 241640 KB Output is correct
12 Correct 762 ms 281164 KB Output is correct
13 Correct 793 ms 319452 KB Output is correct
14 Correct 473 ms 222716 KB Output is correct
15 Correct 768 ms 318456 KB Output is correct
16 Correct 1022 ms 318380 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 133412 KB Output is correct
2 Correct 61 ms 133424 KB Output is correct
3 Correct 63 ms 133412 KB Output is correct
4 Correct 63 ms 133508 KB Output is correct
5 Correct 68 ms 133460 KB Output is correct
6 Correct 66 ms 134472 KB Output is correct
7 Correct 71 ms 135528 KB Output is correct
8 Correct 84 ms 139592 KB Output is correct
9 Correct 75 ms 138512 KB Output is correct
10 Correct 372 ms 187416 KB Output is correct
11 Correct 547 ms 241356 KB Output is correct
12 Correct 754 ms 281996 KB Output is correct
13 Correct 778 ms 282192 KB Output is correct
14 Correct 760 ms 281600 KB Output is correct
15 Correct 756 ms 318236 KB Output is correct
16 Correct 754 ms 318312 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 133412 KB Output is correct
2 Correct 61 ms 133424 KB Output is correct
3 Correct 63 ms 133412 KB Output is correct
4 Correct 63 ms 133508 KB Output is correct
5 Correct 68 ms 133460 KB Output is correct
6 Correct 66 ms 134472 KB Output is correct
7 Correct 71 ms 135528 KB Output is correct
8 Correct 84 ms 139592 KB Output is correct
9 Correct 75 ms 138512 KB Output is correct
10 Correct 372 ms 187416 KB Output is correct
11 Correct 547 ms 241356 KB Output is correct
12 Correct 754 ms 281996 KB Output is correct
13 Correct 778 ms 282192 KB Output is correct
14 Correct 760 ms 281600 KB Output is correct
15 Correct 756 ms 318236 KB Output is correct
16 Correct 754 ms 318312 KB Output is correct
17 Correct 571 ms 241560 KB Output is correct
18 Correct 63 ms 133404 KB Output is correct
19 Correct 62 ms 133392 KB Output is correct
20 Correct 68 ms 133436 KB Output is correct
21 Correct 61 ms 133404 KB Output is correct
22 Correct 62 ms 133456 KB Output is correct
23 Correct 72 ms 134516 KB Output is correct
24 Correct 72 ms 135660 KB Output is correct
25 Correct 85 ms 139552 KB Output is correct
26 Correct 82 ms 138428 KB Output is correct
27 Correct 401 ms 187468 KB Output is correct
28 Correct 773 ms 281996 KB Output is correct
29 Correct 770 ms 282288 KB Output is correct
30 Correct 762 ms 281644 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 186704 KB Output is correct
2 Correct 62 ms 133488 KB Output is correct
3 Correct 61 ms 133400 KB Output is correct
4 Correct 60 ms 133328 KB Output is correct
5 Correct 68 ms 134384 KB Output is correct
6 Correct 74 ms 134408 KB Output is correct
7 Correct 67 ms 134440 KB Output is correct
8 Correct 408 ms 187496 KB Output is correct
9 Correct 415 ms 187492 KB Output is correct
10 Correct 382 ms 186776 KB Output is correct
11 Correct 580 ms 239932 KB Output is correct
12 Correct 62 ms 133332 KB Output is correct
13 Correct 61 ms 133408 KB Output is correct
14 Correct 64 ms 133468 KB Output is correct
15 Correct 61 ms 133460 KB Output is correct
16 Correct 61 ms 133476 KB Output is correct
17 Correct 78 ms 134512 KB Output is correct
18 Correct 90 ms 135600 KB Output is correct
19 Correct 395 ms 187548 KB Output is correct
20 Correct 786 ms 282048 KB Output is correct
21 Correct 575 ms 241640 KB Output is correct
22 Correct 762 ms 281164 KB Output is correct
23 Correct 793 ms 319452 KB Output is correct
24 Correct 473 ms 222716 KB Output is correct
25 Correct 768 ms 318456 KB Output is correct
26 Correct 1022 ms 318380 KB Output is correct
27 Correct 64 ms 133412 KB Output is correct
28 Correct 61 ms 133424 KB Output is correct
29 Correct 63 ms 133412 KB Output is correct
30 Correct 63 ms 133508 KB Output is correct
31 Correct 68 ms 133460 KB Output is correct
32 Correct 66 ms 134472 KB Output is correct
33 Correct 71 ms 135528 KB Output is correct
34 Correct 84 ms 139592 KB Output is correct
35 Correct 75 ms 138512 KB Output is correct
36 Correct 372 ms 187416 KB Output is correct
37 Correct 547 ms 241356 KB Output is correct
38 Correct 754 ms 281996 KB Output is correct
39 Correct 778 ms 282192 KB Output is correct
40 Correct 760 ms 281600 KB Output is correct
41 Correct 756 ms 318236 KB Output is correct
42 Correct 754 ms 318312 KB Output is correct
43 Correct 571 ms 241560 KB Output is correct
44 Correct 63 ms 133404 KB Output is correct
45 Correct 62 ms 133392 KB Output is correct
46 Correct 68 ms 133436 KB Output is correct
47 Correct 61 ms 133404 KB Output is correct
48 Correct 62 ms 133456 KB Output is correct
49 Correct 72 ms 134516 KB Output is correct
50 Correct 72 ms 135660 KB Output is correct
51 Correct 85 ms 139552 KB Output is correct
52 Correct 82 ms 138428 KB Output is correct
53 Correct 401 ms 187468 KB Output is correct
54 Correct 773 ms 281996 KB Output is correct
55 Correct 770 ms 282288 KB Output is correct
56 Correct 762 ms 281644 KB Output is correct
57 Correct 1061 ms 389628 KB Output is correct
58 Correct 404 ms 187480 KB Output is correct
59 Correct 587 ms 241720 KB Output is correct