oj.uz

Submission #1045211

# Submission time Handle Problem Language Result Execution time Memory
1045211 2024-08-05T19:03:38 Z Unforgettablepl Toll (BOI17_toll) C++17
0 / 100
 207 ms 71428 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e10;


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int k,n,m,q;
	cin >> k >> n >> m >> q;
	auto combine = [&](vector<vector<int>> DPa,vector<vector<int>> DPb){
		vector DPres(k,vector(k,INF));
		for(int l=0;l<k;l++){
			for(int r=0;r<k;r++){
				for(int x=0;x<k;x++){
					DPres[l][r]=min(DPres[l][r],DPa[l][x]+DPb[x][r]);
				}
			}
		}
		return DPres;
	};
	int totBlocks = n/k;
	vector lift(totBlocks+1,vector(16,vector(k,vector(k,INF))));
	for(int i=1;i<=m;i++){
		int a,b,t;cin>>a>>b>>t;
		int block = a/k;
		a%=k;b%=k;
		lift[block][0][a][b]=t;
	}
	for(int bit=1;bit<16;bit++){
		for(int i=0;i<=totBlocks;i++){
			if(i+(1<<bit)>totBlocks)continue;
			lift[i][bit]=combine(lift[i][bit-1],lift[i+(1<<(bit-1))][bit-1]);
		}
	}
	for(int i=1;i<=q;i++){
		int a,b;cin>>a>>b;
		int blockA = a/k;a%=k;
		int blockB = b/k;b%=k;
		int tar = blockB-blockA;
		vector res(k,vector(k,0ll));
		for(int bit=0;bit<16;bit++)if(tar&(1<<bit)){
			res=combine(res,lift[blockA][bit]);
			blockA+=(1<<bit);
		}
		if(res[a][b]>=INF or blockA==blockB)cout<<"-1\n";
		else cout<<res[a][b]<<'\n';
	}
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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