oj.uz

Submission #696741

# Submission time Handle Problem Language Result Execution time Memory
696741 2023-02-07T06:44:25 Z vjudge1 Toll (BOI17_toll) C++17
0 / 100
 3000 ms 8168 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=0x3f3f3f3f3f3f3f3f;

ll k, n, m, q, a, b, t;
map<pii, ll> w;

ll len(ll a, ll b){
	ll res[k], tmp[k], x=a/k, xe=b/k, p=x*k;
	for(ll i=0; i<k; i++){
		res[i]=tmp[i]=INF;
		if(w[{a, p+k+i}]){ 
		res[i]=w[{a, p+k+i}];
		}
	}
	p+=k;
	while(p/k<xe){
		for(ll i=0; i<k; i++){
			for(ll j=0; j<k; j++){
				if(res[i] && w[{p+i, p+k+j}]) 
					tmp[j]=min(tmp[j], res[i]+w[{p+i, p+k+j}]);
			}
		}
		for(ll i=0; i<k; i++) res[i]=tmp[i];
		p+=k;
	}
	return res[b%k]==INF? -1: res[b%k];
}

signed main(){
	ios_base::sync_with_stdio(NULL); 
	cin.tie(nullptr); cout.tie(nullptr);
	cin>>k>>n>>m>>q;
	while(m--){
		cin>>a>>b>>t;
		if(a>b) swap(a, b);
		// cout<<a<<" "<<b<<" ";
		w[{a, b}]=t;
		// cout<<w[{a, b}]<<endl;
	}
	while(q--){
		cin>>a>>b;
		cout<<len(a, b)<<endl;
	}
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3029 ms 4348 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 8168 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 212 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 212 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 3029 ms 4348 KB Time limit exceeded
2 Halted 0 ms 0 KB -