제출 #1171764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171764		farica	Toll (BOI17_toll)	C++20	7 / 100	371 ms	589824 KiB

toll

#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";

const int MX = 50005;
const int INF = 1e9;

int lft[5][MX], rght[5][MX], k, n;
vector<pi>Q, f[MX], g[MX];
vi ans;

void div1(int le, int ri, vi v) {
	if(v.empty()) return;
	vi todo[2];
	int m = (le+ri)/2, st = le*k, en = min((ri+1)*k, n);
	for(int t=0; t<k; ++t) {
		for(int j=0; j<en; ++j) lft[t][j] = rght[t][j] = INF;
	}
	int l = m*k, r = min(n, l+k);
	for(int mx = l; mx < r; ++mx) {
		lft[mx-l][mx] = rght[mx-l][mx] = 0;
		for(int i=mx; i>st; --i) {
			for(pi x: g[i]) lft[mx-l][x.first] = min(lft[mx-l][x.first], lft[mx-l][i] + x.second);
		}
		for(int i=mx; i<en-1; ++i) {
			for(pi x: f[i]) rght[mx-l][x.first] = min(rght[mx-l][x.first], rght[mx-l][i] + x.second);
		}
	}
	for(int t: v) {
		int a = Q[t].first, b = Q[t].second;
		if(a/k <= m && b/k > m) {
			for(int mx = l; mx < r; ++mx) {
				if(ans[t] == -1) ans[t] = lft[mx-l][a] + rght[mx-l][b];
				else ans[t] = min(ans[t], lft[mx-l][a] + rght[mx-l][b]);
			}
			continue;
		}
		todo[(a/k)>m].push_back(t);
	}
	div1(le, m, todo[0]);
	div1(m+1, ri, todo[1]);
}

void solve() {
    int m, o;
    cin >> k >> n >> m >> o;
    while(m--) {
		int a, b, w;
		cin >> a >> b >> w;
		f[a].push_back({b,w});
		g[b].push_back({a,w});
	}
	vi v;
	for(int i=0; i<o; ++i) {
		v.push_back(i);
		int a, b;
		cin >> a >> b;
		Q.push_back({a,b});
	}
	ans.assign(o, -1);
	div1(0, (n-1)/k, v);
	for(int x: ans) {
		if(x >= INF) cout << -1 << endl;
		else cout << x << endl;
	}
}

int main(	){
	//freopen("input1.txt", "r", stdin)   
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	    
    int t = 1;
    while (t--) solve();
}

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