Submission #415169

#	Time	Username	Problem	Language	Result	Execution time	Memory
415169		Blagojce	Toll (BOI17_toll)	C++11	56 / 100	401 ms	170596 KiB

toll

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;

mt19937 _rand(time(NULL));
const int mxn = 1e5;

int n, k, m, q;


vector<pii> g[mxn];


ll sparse[mxn][17][5][5];


ll aux[5][5];

void fillaux(int u, int p){
	fr(i, 0, k){
		fr(j, 0, k){
			aux[i][j] = inf;
		}
	}
	fr(i, 0, k){
		fr(j, 0, k){
			ll w = sparse[u][p][i][j];
			int pos = (u+(1<<p)-1)*k + j;
			
			for(auto v : g[pos]){
				int jp = v.st%k;
				aux[i][jp] = min(aux[i][jp], w + v.nd);
			}
		}
	}
}
void combine(int u, int p){
	int subu = u;
	int subv = u + (1<<p);
	
	fr(mid, 0, k){
		fr(i, 0, k){
			fr(j, 0, k){
				sparse[subu][p+1][i][j] = min(sparse[subu][p+1][i][j], aux[i][mid] + sparse[subv][p][mid][j]);	
			}
		}
	}
}


void update(int u, int p){
	if(u + (1<<p) > n) return;
	fillaux(u, p-1);
	combine(u, p-1);
}


ll dist[5];
ll dist2[5];
ll query(int a, int b){
	int S = a/k;
	int E = b/k;
	if(S == E) return -1;
	
	
	fr(i, 0, k) dist[i] = inf;
	dist[a%k] = 0;
	
	for(int p = 16; p >= 0; p --){
		while(S + (1<<p) <= E){
			
			fr(i, 0, k) dist2[i] = inf;
			fr(i, 0, k){
				fr(j, 0, k){
					ll w = sparse[S][p][i][j];
					
					int pos = (S+(1<<p)-1)*k + j;
					for(auto v : g[pos]){
						int jp = v.st%k;
						dist2[jp] = min(dist2[jp], dist[i] + w + v.nd);
					}
				}
			}
			fr(i, 0, k) dist[i] = dist2[i];
			S += (1<<p);
		}
	}
	
	if(dist[b%k] == inf) return -1;
	else return dist[b%k];
	
}


void solve(){
	cin >> k >> n >> m >> q;
	
	while(n % k != 0) ++n;
	
	fr(i, 0, m){ 
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
	}
	fr(u, 0, n/k){
		fr(p, 0, 17){
			fr(i, 0, k){
				fr(j, 0, k){
					sparse[u][p][i][j] = inf;
				}
			}
		}
	}
	fr(u, 0, n/k){
		fr(i, 0, k){
			sparse[u][0][i][i] = 0;
		}
	}
	fr(p, 1, 17){
		fr(u, 0, n/k){
			update(u, p);
		}
	}
	while(q--){
		int a, b;
		cin >> a >> b;
		cout<<query(a, b)<<endl;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

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