Submission #1264134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264134		_rain_	Toll (BOI17_toll)	C++20	100 / 100	165 ms	173188 KiB

toll

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i , a , b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define MASK(x) ((LL)(1) << (x))
#define BIT(mask , x) (((mask)>>(x))&(1))
#define sz(x) (int)(x).size()

template<class T1 , class T2>	
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() ,data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}


const int N = (int) 5e4;
const int inf = (int) 1e9 + 7;
const int MAXLOG = (int) 16;
const int MAXK = (int) 5;
	int dp[N + 2][MAXLOG + 2][MAXK + 2][MAXK + 2];

	int n , m , q , k;

	void combine(int res[MAXK+2][MAXK+2] , int x[MAXK+2][MAXK+2] , int y[MAXK+2][MAXK+2]){
		for(int t = 0; t <= k; ++t){
			for(int i = 0; i <= k; ++i){
				for(int j = 0; j <= k; ++j){
					minimize(res[i][j] , x[i][t] + y[t][j]);
				}
			}
		}
		return ;
	}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ; 
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}	

		cin >> k >> n >> m >> q;
		memset(dp , 0x3f , sizeof dp);
		for(int i = 1; i <= m; ++i){
			int a , b , w;
			cin >> a >> b >> w;
			minimize(dp[a / k][0][a % k][b % k] ,  w);
		} 
		
		int tt = (n / k) + (n % k != 0);
		

		for(int j = 1; j <= MAXLOG; ++j){
			for(int i = 0; i + MASK(j) - 1 <= tt; ++i){
				combine(dp[i][j] , dp[i][j - 1] , dp[i + MASK(j - 1)][j - 1]);
			}
		}
		
		while(q--){
			int a , b; cin >> a >> b;
			int ans[MAXK + 2][MAXK + 2] = {};
			int tmp[MAXK + 2][MAXK + 2] = {};
			
			int cur = a / k;
			memset(ans,0x3f,sizeof ans);
			for(int i = 0; i <= MAXK; ++i) ans[i][i] = 0;
			
			for(int i = MAXLOG; i >= 0; --i){
				if (cur + MASK(i) <= b / k){
					
					memset(tmp,0x3f,sizeof tmp);
					combine(tmp , ans , dp[cur][i]);
					
					for(int j = 0; j <= k; ++j){
						for(int t = 0; t <= k; ++t) ans[j][t] = tmp[j][t];
					}
					cur += MASK(i);
				}
			}
			LL res = inf;
			minimize(res , ans[a%k][b%k]);
			if (res == inf) res = -1;
			cout << res << '\n';
		}
	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:53:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:54:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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