Submission #696812

#	Time	Username	Problem	Language	Result	Execution time	Memory
696812		nhphan0505	Toll (BOI17_toll)	C++17	0 / 100	564 ms	239868 KiB

toll

#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+=(i<<1);
			}
		cout<<(res[a%k][b%k]==INF? -1: res[a%k][b%k])<<endl;
	}
    return 0;
}	

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44