Submission #405872

#	Time	Username	Problem	Language	Result	Execution time	Memory
405872		thomas_li	Toll (BOI17_toll)	C++17	7 / 100	3050 ms	12564 KiB

toll

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int MM = 5e4+5;
int n,o,k,m; ll ans[MM]; ll dp_forward[MM],dp_back[MM]; vector<pi> adj[MM],radj[MM];
vector<int> comp[MM];
void dfs(int u){
	for(auto [v,w] : adj[u]){
		dp_forward[v] = min(dp_forward[v],dp_forward[u]+w);
		dfs(v);
	}
}

void dfs1(int u){
	for(auto[v,w]:radj[u]){
		dp_back[v] = min(dp_back[v],dp_back[u]+w);
		dfs1(v);
	}
}

void rec(int l, int r,vector<array<int,5>>& qu){
	//cout << "HERE " << l << " " << r << "\n";
	if(qu.empty()) return;
	if(l == r){
		for(auto[ak,bk,a,b,i]:qu){
			ans[i] = -1;
		}
		return;
	}
	memset(dp_forward,0x3f,sizeof dp_forward); memset(dp_back,0x3f,sizeof dp_back);
	//for(int i = l; i <= r; i++) dp_forward[i] = dp_back[i] = 1e9;
	int mid = (l+r)/2;
	for(int u : comp[mid]){
		// try each node
		dp_forward[u] = dp_back[u] = 0;
		dfs(u);
		dfs1(u);
		//cout << u << " ";
		for(auto[ak,bk,a,b,i]:qu){
			if(ak <= mid && mid < bk){
				//cout << "qu: " << ak << " " << bk << " " << a << " " << b << " " << u << "\n";
				ans[i] = min(ans[i],dp_back[a] + dp_forward[b]);
				continue;
			}
		}
	}
	//cout << "\n";
	vector<array<int,5>> nxt[2];
	for(auto[ak,bk,a,b,i]:qu){
		if(ak <= mid && mid < bk){			
			continue;
		}
		nxt[ak > mid].push_back({ak,bk,a,b,i});
	}
	rec(l,mid,nxt[0]); rec(mid+1,r,nxt[1]);
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> k >> n >> m >> o; memset(ans,0x3f,sizeof ans);
	for(int i = 0; i < m; i++){
		int a,b,t; cin >> a >> b >> t; 
		adj[a].emplace_back(b,t); radj[b].emplace_back(a,t);
	}
	for(int i = 0; i < n; i++) comp[i/k].emplace_back(i);
	vector<array<int,5>> qu;
	for(int i = 0; i < o; i++){
		int a,b; cin >> a >> b;
		if(a/k == b/k || a/k > b/k){
			ans[i] = -1;
			continue;
		}
		qu.push_back({a/k,b/k,a,b,i});
	}
	rec(0,(n-1)/k,qu);
	for(int i = 0; i < o; i++) cout << (ans[i]>=1e9 ? -1 : ans[i]) << "\n";
}

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