제출 #240309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240309		alishahali1382	Toll (BOI17_toll)	C++14	100 / 100	159 ms	28152 KiB

toll

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=50010, LOG=20;

int n, m, k, q, u, v, x, y, t, a, b, ans;
int A[MAXN];
vector<piii> E[MAXN];

struct Node{
	int dist[5][5], st=-1;
	Node(){
		memset(dist, 31, sizeof(dist));
	}
} seg[MAXN<<2];

Node Merge(Node x, Node y){
	if (x.st==-1) return y;
	if (y.st==-1) return x;
	Node z;
	z.st=x.st;
	for (int i=0; i<k; i++) for (int j=0; j<k; j++) for (piii p:E[y.st-1]){
		z.dist[i][j]=min(z.dist[i][j], x.dist[i][p.first.first]+p.second+y.dist[p.first.second][j]);
	}
	return z;
}

void Build(int id, int tl, int tr){
	seg[id].st=tl;
	if (tr-tl==1){
		for (int i=0; i<k; i++) seg[id].dist[i][i]=0;
		return ;
	}
	int mid=(tl+tr)>>1;
	Build(id<<1, tl, mid);
	Build(id<<1 | 1, mid, tr);
	seg[id]=Merge(seg[id<<1], seg[id<<1 | 1]);
//	debug2(tl, tr)
//	for (int i=0; i<k; i++) for (int j=0; j<k; j++) cerr<<seg[id].dist[i][j]<<" \n"[j==k-1];
}

Node Get(int id, int tl, int tr, int l, int r){
	if (r<=tl || tr<=l) return seg[0];
	if (l<=tl && tr<=r) return seg[id];
	int mid=(tl+tr)>>1;
	return Merge(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>k>>n>>m>>q;
	while (m--){
		cin>>u>>v>>x;
		E[u/k].pb({{u%k, v%k}, x});
	}
	Build(1, 0, (n+k-1)/k);
	while (q--){
		cin>>u>>v;
		Node tmp=Get(1, 0, (n+k-1)/k, u/k, v/k+1);
		ans=tmp.dist[u%k][v%k];
		if (ans>5e8) ans=-1;
		cout<<ans<<'\n';
	}
	
	
	return 0;
}
/*
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