Submission #342576

#	Time	Username	Problem	Language	Result	Execution time	Memory
342576		ronnith	Toll (BOI17_toll)	C++14	100 / 100	205 ms	12936 KiB

toll

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i = (a);i < (b);i ++)
#define ROF(i,a,b) for(int i = (a);i >= (b);i --)
#define trav(a, b) for(auto a : (b))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()

#define pb push_back
#define mk make_pair
#define mt make_tuple
#define f first
#define s second

using namespace std;

typedef long long ll;

int k, n, m, o, ans[10000], dat[50000][5];
vector<pair<int, int>> front[50000], back[50000];

void divi(int l, int r, const vector<tuple<int, int, int>> query){
	if(l == r){
		trav(_,query){
			int id,a,b;tie(id,a,b) = _;
			ans[id] = -1;
		}
	} else {
		int mid = l + (r - l) / 2;
		ROF(i,mid,l){
			FOR(j,i * k, min(i * k + k,n)){
				if(i == mid){
					FOR(le,0,k){
						if(j != le + i * k) dat[j][le] = -1;
						else dat[j][le] = 0;
					}
				} else {
					FOR(le,0,k){
						dat[j][le] = -1;
						trav(e, front[j]){
							if(dat[e.f][le] != -1){
								dat[j][le] = ((dat[j][le] == -1 || dat[j][le] > e.s + dat[e.f][le]) ? e.s + dat[e.f][le] : dat[j][le]);
							}
						}
					}
				}
			}
		}
		FOR(i,mid + 1,r + 1){
			FOR(j,(i * k),min((i * k) + k, n)){
				if(i == mid + 1){
					FOR(le,0,k){
						if(j != le + i * k) dat[j][le] = -1;
						else dat[j][le] = 0;
					}
				} else {
					FOR(le,0,k){
						dat[j][le] = -1;
						trav(e, back[j]){
							if(dat[e.f][le] != -1){
								dat[j][le] = ((dat[j][le] == -1 || dat[j][le] > e.s + dat[e.f][le]) ? e.s + dat[e.f][le] : dat[j][le]);
							}
						}
					}
				}
			}
		}
		vector<tuple<int, int, int>> todo[2];
		trav(_, query){
			int id,lx,rx;tie(id,lx,rx) = _;
			// if(lx == 0 && rx == 5)cerr << "yes";
			if(lx / k <= mid && rx / k > mid){
				ans[id] = -1;
				FOR(i,mid * k,min(mid * k + k, n)){
					trav(e, front[i]){
						// if(lx == 0 && rx == 5)cerr << i << ' ' << e.f << '\n';
						if(dat[lx][i - mid * k] == -1 || dat[rx][e.f - mid * k - k] == -1) continue;
						if(ans[id] == -1)ans[id] = dat[lx][i - mid * k] + e.s + dat[rx][e.f - mid * k - k];
						else ans[id] = min(ans[id], dat[lx][i - mid * k] + e.s + dat[rx][e.f - mid * k - k]);
					}
				}
			} else todo[rx / k > mid].pb(_);
		}
		divi(l,mid,todo[0]);divi(mid + 1,r,todo[1]);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin >> k >> n >> m >> o;
	
	FOR(i,0,m){
		int x, y, w;
		cin >> x >> y >> w;
		front[x].pb(mk(y, w));
		back[y].pb(mk(x, w));
	}

	vector<tuple<int, int, int>> query;
	FOR(i,0,o){
		int a, b;
		cin >> a >> b;
		query.pb(mt(i, a, b));
	}

	divi(0,(n - 1) / k,query);

	FOR(i,0,o){
		cout << ans[i] << '\n';
	}

	return 0;
}

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