oj.uz

Submission #1045206

# Submission time Handle Problem Language Result Execution time Memory
1045206 2024-08-05T18:59:10 Z Unforgettablepl Toll (BOI17_toll) C++17
7 / 100
 221 ms 72024 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)cout<<"-1\n";
		else cout<<res[a][b]<<'\n';
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 72016 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 1744 KB Output is correct
6 Correct 3 ms 1892 KB Output is correct
7 Correct 3 ms 1884 KB Output is correct
8 Correct 221 ms 72024 KB Output is correct
9 Correct 203 ms 71872 KB Output is correct
10 Correct 186 ms 71248 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 72016 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 1744 KB Output is correct
6 Correct 3 ms 1892 KB Output is correct
7 Correct 3 ms 1884 KB Output is correct
8 Correct 221 ms 72024 KB Output is correct
9 Correct 203 ms 71872 KB Output is correct
10 Correct 186 ms 71248 KB Output is correct
11 Incorrect 175 ms 61776 KB Output isn't correct
12 Halted 0 ms 0 KB -