Submission #1287261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287261		herominhsteve	Toll (BOI17_toll)	C++20	0 / 100	108 ms	77740 KiB

toll

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "fee"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 50'005;
const int LOG = 16;
const long long INF = (long long) 1e16 + 15092007;

struct Matrix{
	int n,m;
	vector<vector<long long>> matrix;
	Matrix(int N=0,int M=0){
		n=N;
		m=M;
		if (n>0 and m>0){
			matrix.assign(n,vector<long long>(m,INF));
			for (int i=0;i<n;i++) matrix[i][i]=0;
		}
	}
	Matrix operator * (const Matrix &other) const{
		Matrix res(n,other.m);
		
		for (int i=0;i<n;i++){
			for (int j=0;j<other.m;j++){
				for (int k=0;k<m;k++){
					minimize(res.matrix[i][j],matrix[i][k] + other.matrix[k][j]);
				}
			}
		}
		return res;
	}
};

int K,n,m,q;

int BLK;

// ? dp[i].matrix[x][y]: min cost to go from i * K + x -> (i+1)*K + y
vector<Matrix> dp;
vector<vector<Matrix>> sparse;

void init(){
	cin>>K>>n>>m>>q;
	BLK = (n+K-1) / K;
	dp.assign(BLK,Matrix(K,K));
	sparse.resize(LOG+1,vector<Matrix>(BLK));
	for (int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		dp[u / K].matrix[u % K][v % K] = w;
	}
	for (int i=0;i<BLK;i++) sparse[0][i] = dp[i];

	for (int k=1;k<=LOG;k++){
		for (int i=0;i + (1<<k) <= BLK; i++){
			sparse[k][i] = sparse[k-1][i] * sparse[k-1][i + (1<<(k-1))];
		}
	}
}

// ? get [l,r+1] since matrix compute up to r + 1
inline Matrix getMatrix(int l, int r){
    if (l == r) return sparse[0][l];
    int len = r - l + 1;
    int k = 31 - __builtin_clz(len);
    return sparse[k][l] * sparse[k][r - (1<<k) + 1];
}


void sol(){
	while (q--){
		int u,v;
		cin>>u>>v;
		if ((u/K) >= (v/K)){
			cout<<-1<<el;
			continue;
		}
		int L = u / K;
		int R = v / K;
		long long res = getMatrix(L,R-1).matrix[u % K][v % K];
		cout<< (res == INF ? -1 : res)<<el;
	}
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

toll.cpp: In function 'void setup()':
toll.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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