Submission #169949

#	Time	Username	Problem	Language	Result	Execution time	Memory
169949		moonrabbit2	Toll (BOI17_toll)	C++17	100 / 100	165 ms	12284 KiB

toll

#include <bits/stdc++.h>
#define x first
#define y second
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef vector<vector<ll>> mat;
const ll mod=1e9+7;
const int N=5e4+5;
int n,m,q,k;
vector<tii> edge[N];
struct node{
	int d[5][5]={0};
};
node tree[4*N];
void init(int nd,int l,int r){
	if(l==r){
		for(int i=0;i<k;i++){
			for(int j=0;j<k;j++){
				if(i!=j) tree[nd].d[i][j]=1e9;
			}
		}
		return;
	}
	int m=(l+r)>>1;
	init(nd<<1,l,m); init(nd<<1|1,m+1,r);
	for(int i=0;i<k;i++) for(int j=0;j<k;j++){
		tree[nd].d[i][j]=1e9;
	}
	for(auto &it : edge[m]){
		int u=get<0>(it)%k,v=get<1>(it)%k,c=get<2>(it);
		for(int i=0;i<k;i++) for(int j=0;j<k;j++){
			tree[nd].d[i][j]=min(tree[nd].d[i][j],tree[nd<<1].d[i][u]+c+tree[nd<<1|1].d[v][j]);
		}
	}
}
node qry(int nd,int l,int r,int s,int e){
	node res;
	if(s<=l&&r<=e) return tree[nd];
	int m=(l+r)>>1;
	if(e<=m) return qry(nd<<1,l,m,s,e);
	if(m<s) return qry(nd<<1|1,m+1,r,s,e);
	node n1=qry(nd<<1,l,m,s,e),n2=qry(nd<<1|1,m+1,r,s,e);
	for(int i=0;i<k;i++) for(int j=0;j<k;j++){
		res.d[i][j]=1e9;
	}
	for(auto &it : edge[m]){
		int u=get<0>(it)%k,v=get<1>(it)%k,c=get<2>(it);
		for(int i=0;i<k;i++) for(int j=0;j<k;j++){
			res.d[i][j]=min(res.d[i][j],n1.d[i][u]+c+n2.d[v][j]);
		}
	}
	return res;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>k>>n>>m>>q;
	for(int u,v,c,i=1;i<=m;i++){
		cin>>u>>v>>c;
		edge[u/k].emplace_back(u,v,c);
	}
	init(1,0,(n-1)/k);
	for(int u,v,i=1;i<=q;i++){
		cin>>u>>v;
		if(u/k>=v/k){
			cout<<"-1\n";
			continue;
		}
		node res=qry(1,0,(n-1)/k,u/k,v/k);
		if(res.d[u%k][v%k]==1e9) cout<<"-1\n";
		else cout<<res.d[u%k][v%k]<<"\n";
	}
    return 0;
}

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