Submission #860733

#	Time	Username	Problem	Language	Result	Execution time	Memory
860733		phoenix0423	Toll (BOI17_toll)	C++17	100 / 100	192 ms	18256 KiB

toll

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 5e4 + 5;
const int INF = 1e9;
const int sqrtn = 500;
int k, n, m, o;
int len;
vector<pll> adj[maxn];

struct node{
	vector<vector<int>> dist;
	void init(){
		dist.resize(k);
		for(int i = 0; i < k; i++){
			dist[i].resize(k, INF);
			dist[i][i] = 0;
		}
	}
	node(){
		dist = vector<vector<int>>(k, vector<int>(k, INF));
	}
	node(vector<vector<int>> _dist) : dist(_dist){}
} st[maxn * 4];

node add(int m, node a, node b){
	vector<vector<int>> ndist(k, vector<int>(k, INF));
	for(int i = 0; i < k; i++){
		for(int j = 0; j < k; j++){
			for(int pos = 0; pos < k; pos++){
				for(auto [x, w] : adj[m * k + pos]){
					ndist[i][j] = min(ndist[i][j], a.dist[i][pos] + b.dist[x - m * k - k][j] + w);
				}
			}
		}
	}
	return node(ndist);
}

void build(int v = 1, int l = 0, int r = len){
	if(l == r){
		st[v].init();
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m + 1, r);
	// cout<<"combine : "<<l<<" "<<m<<" "<<r<<"\n";
	st[v] = add(m, st[v * 2], st[v * 2 + 1]);
}

node qry(int l, int r, int v = 1, int L = 0, int R = len){
	if(l <= L && r >= R) return st[v];
	int m = (L + R) / 2;
	if(r <= m) return qry(l, r, v * 2, L, m);
	else if(l > m) return qry(l, r, v * 2 + 1, m + 1, R);
	else return add(m, qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}

int main(void){
	fastio;
	cin>>k>>n>>m>>o;
	len = n / k;
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin>>a>>b>>c;
		adj[a].eb(b, c);
	}
	build();
	for(int i = 0; i < o; i++){
		int a, b;
		cin>>a>>b;
		node mat = qry(a / k, b / k);
		cout<<(mat.dist[a % k][b % k] < INF ? mat.dist[a % k][b % k] : -1)<<"\n";
	}
}

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