Submission #878299

#	Time	Username	Problem	Language	Result	Execution time	Memory
878299		manizare	Toll (BOI17_toll)	C++14	0 / 100	3101 ms	23868 KiB

toll

#include <bits/stdc++.h>
 
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define int long long
#define sz(v) (int)v.size()
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e4 + 10 , inf = 1e18 , mod = 998244353 ;
int k , n , m , q;
int  dis[maxn][5] , d[maxn] , mark[maxn] ;
vector <pii> G[maxn] ;
struct node{
	int s[5][5]  ,l , r;  
};
vector <int> his ; 
void dij(int v){
	priority_queue <pii> pq ;
	pq.push({0 , v}) ;
	d[v] = 0;
	while(pq.size()){
		int v = pq.top().S ; pq.pop() ;
		if(mark[v] == 1)continue ;
		his.pb(v);
		mark[v] = 1;
		for(pii u : G[v]){
			if(d[u.F] > d[v]+u.S){
				d[u.F] = d[v] + u.S ;
				pq.push({-d[u.F] , u.F}) ;
			}
		}
	}
}
void cle(){
	for(int v : his){
		d[v] = inf ; 
		mark[v] =0 ; 
	}
}

node seg[4*maxn]  ;
node operator+(node a,node b){
	node res ; 
	int l =a.l , r = b.r, mid = a.r ; 
	res.l = l ;
	res.r = r ;
	for(int i = 0 ;i  < k  ;i++){
		for(int j =0 ; j < k ; j++){
			G[l*k+i].pb({mid*k+j , a.s[i][j]}) ; 
			G[mid*k+i].pb({(mid+1)*k+j , dis[mid*k+i][j]});
			G[(mid+1)*k+i].pb({r*k+j , b.s[i][j]}); 
		}
	}
	for(int i =0 ; i < 5 ; i++){
		dij(l*k+i) ;
		for(int j =0 ; j < 5 ;j ++){
			res.s[i][j] = d[r*k+j] ;
		}
		cle();
	}
	for(int i =0  ; i < k ; i++){
		G[l*k+i].clear();
		G[mid*k+i].clear() ;
		G[(mid+1)*k].clear() ;
	} 
	return res ;
}

void bui(int p = 1 , int l = 0 , int r = n/k){
	int pl = p<<1 , pr = p << 1 | 1 , mid = (l+r)/2 ;
	for(int i =0 ; i < k ; i++){
		for(int j =0 ; j < k ; j++){
			seg[p].s[i][j] = inf ; 
		}
	}
	if(l == r){
		seg[p].l = l , seg[p].r=  r ;
		for(int i  =0 ;i < k ; i++){
			seg[p].s[i][i] = 0 ;
		}
		return ;
	}
	bui(pl , l, mid) ;
	bui(pr, mid+1,r);
	seg[p] = seg[pl] + seg[pr] ;
}
node que(int le ,int ri , int p = 1,int l = 0 , int r = n/k){
	int pl = p<<1 , pr = p << 1 | 1 , mid = (l+r)/2 ;
	if(le <= l && r <= ri){
		return seg[p] ;
	}
	if(mid >= ri){
		return que(le,ri,pl,l,mid);
	}
	if(mid < le){
		return que(le , ri ,pr,mid+1,r);
	}
	return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r) ;
}

signed main() {
    ios :: sync_with_stdio(0); cin.tie(0);
	cin >> k >> n >> m >> q ;
	for(int i =0 ; i <= n; i++){
		for(int j =0 ; j < k ; j++){
			dis[i][j] = inf ; 
		}
	}
	for(int i = 1; i <= m; i++){
		int v , u , c;
		cin >> v >> u >> c ;
		dis[v][u%k] = min(dis[v][u%k] , c) ;
	}
	for(int i =0 ; i <= n+k; i++){
		d[i] = inf ;
	}
	bui();
	while(q--){
		int v ,u  ;
		cin >> v >> u ;
		if(v/k >= u/k){
			cout << -1 << "\n";
			continue ;
		}
		int ans= (que(v/k , u/k)).s[v%k][u%k];
		if(ans == inf){
			cout << -1 << "\n";
		}else{
			cout << ans << "\n";
		}
	}
}
/* 
 
 
*/

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