oj.uz

Submission #696763

# Submission time Handle Problem Language Result Execution time Memory
696763 2023-02-07T08:00:55 Z vjudge1 Toll (BOI17_toll) C++17
7 / 100
 726 ms 290088 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;
	}
	
	static matrix identity(ll n){
		matrix res(n, n);
		for(ll i=0; i<n; i++) res[i][i]=1;
		return res;
	}
	
	matrix operator *(const matrix b){
		matrix a=*this, res(a.n, b.m, INF);
		// cout<<b.n<<" "<<b.m<<endl;
		for(ll i=0; i<a.n; i++)
			for(ll j=0; j<b.m; j++)
				for(ll k=0; k<a.m; k++) 
					if(a[i][k]!=INF && b[k][j]!=INF)
						res[i][j]=min(res[i][j], a[i][k]+b[k][j]);
		return res;
	}
};

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

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<20; j++)  p[i][j]=matrix(k, k, INF);
		
	while(m--){
		cin>>a>>b>>t;
		if(a>b) swap(a, b);
		if(a/k+1==b/k)p[a/k][0][a%k][b%k]=t;
	}
	
	for(ll i=0; i<n; i++) up[i][0]=i+1;
	
	for(ll i=1; i<20; i++)
		for(ll j=0; j<n; j++){
			up[j][i]=up[up[j][i-1]][i-1];
			p[j][i]=p[j][i-1]*p[up[j][i-1]][i-1];
		}
		
	while(q--){
		cin>>a>>b;
		ll now=a/k, l=b/k-a/k;
		bool bl=0;
		matrix res(k, 1, INF);
		res[b%k][0]=0;
		// cout<<res;
		for(ll i=0; i<20; i++)
			if(l&(1<<i)){
				res=p[now][i]*res;
				now=up[now][i];
				bl=1;
			}
		cout<<(res[a%k][0]==INF? -1: res[a%k][0])<<endl;
	}
    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:80:8: warning: variable 'bl' set but not used [-Wunused-but-set-variable]
   80 |   bool bl=0;
      |        ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 227536 KB Output is correct
2 Correct 72 ms 156880 KB Output is correct
3 Correct 73 ms 156872 KB Output is correct
4 Correct 72 ms 156876 KB Output is correct
5 Correct 86 ms 158276 KB Output is correct
6 Correct 79 ms 158216 KB Output is correct
7 Correct 77 ms 158284 KB Output is correct
8 Correct 537 ms 227280 KB Output is correct
9 Correct 560 ms 227416 KB Output is correct
10 Correct 508 ms 227352 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 156896 KB Output is correct
2 Incorrect 75 ms 156876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 156896 KB Output is correct
2 Incorrect 75 ms 156876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 227536 KB Output is correct
2 Correct 72 ms 156880 KB Output is correct
3 Correct 73 ms 156872 KB Output is correct
4 Correct 72 ms 156876 KB Output is correct
5 Correct 86 ms 158276 KB Output is correct
6 Correct 79 ms 158216 KB Output is correct
7 Correct 77 ms 158284 KB Output is correct
8 Correct 537 ms 227280 KB Output is correct
9 Correct 560 ms 227416 KB Output is correct
10 Correct 508 ms 227352 KB Output is correct
11 Incorrect 726 ms 290088 KB Output isn't correct
12 Halted 0 ms 0 KB -