제출 #1011585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011585		ByeWorld	Toll (BOI17_toll)	C++14	100 / 100	164 ms	54184 KiB

toll

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
typedef pair<vector<vector<int>>, int> iipii;
const int MAXN = 5e4+20;
const int MAXA = 9e3+20;
const ll INF = 1e18+10;
const int LOG = 19;
const int MOD = 1e15;
const int SQRT = 450;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
void chmn(int &a, int b){
	a = min(a, b);
}
int n, m, q, k;
vector<vector<int>> adj[MAXN];
vector<vector<int>> NOL;

struct seg {
	vector<vector<int>> st[4*MAXN];
	vector<vector<int>> mrg(vector<vector<int>> a, vector<vector<int>> b){
		vector<vector<int>> ret = NOL;
		for(int i=0; i<k; i++){
			for(int j=0; j<k; j++){
				for(int p=0; p<k; p++){
					chmn(ret[i][j], a[i][p]+b[p][j]);
				}
			}
		}
		return ret;
	}
	void bd(int id, int l, int r){
		if(l==r){
			st[id] = adj[l]; return; 
		}
		bd(lf, l, md); bd(rg, md+1, r);
		st[id] = mrg(st[lf], st[rg]);
		return;
	}
	iipii que(int id, int l, int r, int x, int y){
		if(x<=l && r<=y) return iipii(st[id], 1);
		if(r<x || y<l) return iipii(NOL, -1);
		iipii le = que(lf,l,md,x,y);
		iipii ri = que(rg,md+1,r,x,y);
		if(le.se==-1) return ri;
		if(ri.se==-1) return le;
		return iipii(mrg(le.fi, ri.fi), 1);
	}
} A;

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> k >> n >> m >> q;
	vector<int> TEM(k, INF); for(int i=0; i<k; i++) NOL.pb(TEM);
	for(int i=1; i<=n; i++) adj[i] = NOL;
	for(int i=1; i<=m; i++){
		int x, y, w; cin >> x >> y >> w;
		// cout << x/k+1 << " p\n";
		chmn(adj[x/k+1][x%k][y%k], w);
	}
	A.bd(1, 1, n);
	while(q--){
		int a, b; cin >> a >> b;
		if(a/k==b/k){
			cout << "-1\n"; continue;
		}
		// cout << a/k+1 << ' ' << b/k << " que\n";
		vector<vector<int>> ret = A.que(1,1,n,a/k+1, b/k).fi;
		// cout << q << ' ' << ret[a%k][b%k] << " pp\n";
		cout << (ret[a%k][b%k]>=MOD ? -1 : ret[a%k][b%k]) << '\n';
	}
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
*/

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