Submission #1287266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287266		herominhsteve	Toll (BOI17_toll)	C++20	100 / 100	126 ms	23868 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));
		}
	}
	inline void toUnit(){
		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;

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

struct SegmentTree{
	int n;
	vector<Matrix> st;

	SegmentTree(int N=0){
		n = N;
		if (n>0){
			st.resize(4 * n + 4,Matrix(K,K));
		}
	}

	void build(int node,int l,int r,const vector<Matrix> &a){
		if (l==r){
			st[node] = a[l];
			return;
		}
		int mid = (l+r)>>1;
		build(2*node,l,mid,a);
		build(2*node+1,mid+1,r,a);
		st[node] = st[2*node] * st[2*node+1];
	}

	void build(const vector<Matrix> &a){
		build(1,0,n-1,a);
	}

	Matrix getMatrix(int node,int l,int r,int wanted_l,int wanted_r){
		if (wanted_r < l or r < wanted_l){
			Matrix unitMatrix(K,K);
			unitMatrix.toUnit();
			return unitMatrix;
		}
		if (wanted_l <= l and r <= wanted_r) return st[node];
		int mid = (l+r)>>1;
		return getMatrix(2*node,l,mid,wanted_l,wanted_r) * getMatrix(2*node+1,mid+1,r,wanted_l,wanted_r);
	}

	Matrix getMatrix(int l,int r){
		return getMatrix(1,0,n-1,l,r);
	}

};

void sol(){
	SegmentTree st(BLK);
	st.build(dp);

	while (q--){
		int u,v;
		cin>>u>>v;
		if (u==v){
			cout<<0<<el;
			continue;
		}
		if ((u/K) >= (v/K)){
			cout<<-1<<el;
			continue;
		}
		int L = u / K;
		int R = v / K;
		long long res = st.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: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44