Submission #388393

#	Time	Username	Problem	Language	Result	Execution time	Memory
388393		soroush	Toll (BOI17_toll)	C++17	100 / 100	107 ms	28740 KiB

toll

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair < int , int > pii;
 
const int maxn = 5e4 + 10;
const ll inf = 1e10;
 
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
 
#define fuck(x) for(int i = 0 ; i < 5 ; i ++)for(int j = 0 ; j < 5 ; j ++)x[i][j] = inf;
 
int k , n , m , q;
 
struct node{
	ll dist[5][5];
	friend node operator +(node l , node r){
		node v;
		fuck(v.dist);
		for(int i = 0 ; i < 5 ; i ++)for(int k = 0 ; k < 5 ; k ++)for(int j = 0 ; j < 5 ; j ++)
			v.dist[i][k] = min(v.dist[i][k] , l.dist[i][j] + r.dist[j][k]);
		return v;
	}
}seg[maxn<<2];
 
vector < pii > adj[maxn];
 
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
 
void build(int v = 1 , int l = 0 , int r = (n + k - 1)/k){
	if(r - l == 1){
		fuck(seg[v].dist);
		for(int s = 0 ; s < k ; s ++)
			for(auto u : adj[l * k + s])
				seg[v].dist[s][u.first%k] = u.second;
		return;
	}
	build(lc , l , mid);
	build(rc , mid , r);
	seg[v] = seg[lc] + seg[rc];
}
 
node get(int L , int R , int v = 1 , int l = 0 , int r = (n + k - 1)/k){
	if(L <= l and r <= R)
		return seg[v];
	if(L < mid and R <= mid)
		return get(L , R , lc , l , mid);
	if(L >= mid)
		return get(L , R , rc , mid , r);
	return get(L , R , lc , l , mid) + get(L , R , rc , mid , r);
}
 
int32_t main(){
	migmig;
	cin >> k >> n >> m >> q;
	for(int i = 1 ; i <= m ; i ++){
		int u , v , w;
		cin >> u >> v >> w;
		adj[u].pb({v , w});
	}
	build();
	while(q --){
		int u , v;
		cin >> u >> v;
		if(u > v or u/k == v/k){
			cout << -1 << endl;
			continue;
		}
		if(u == v){
			cout << 0 << endl;
			continue;
		}
		auto res = get(u/k , v/k);
		cout << ((res.dist[u%k][v%k] == inf) ? -1 : res.dist[u%k][v%k]) << endl;
	}
	return(0);
}

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