제출 #408620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408620		kwongweng	Toll (BOI17_toll)	C++17	100 / 100	201 ms	94276 KiB

toll

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#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 ms memset
#define pb push_back
#define F first
#define S second
ll MOD = 1000000007;
ll INF = 1000000000;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
	if (a == 0) return b;
	if (a == 1) return 1;
	return gcd(b%a, a);
}

int k;
struct piece{
	int dist[5][5];
	void init(){
		ms(dist, -1, sizeof(dist));
	}
	void upd(int a, int b, int val){
		if (dist[a][b] == -1) dist[a][b] = val;
		else dist[a][b] = min(dist[a][b], val);
	}
};
piece comb(piece p1, piece p2){
	piece ans; ans.init();
	FOR(i, 0, k){
		FOR(j, 0, k){
			FOR(l, 0, k){
				if (p1.dist[i][l] == -1 || p2.dist[l][j] == -1) continue; 
				ans.upd(i, j, p1.dist[i][l] + p2.dist[l][j]);
			}
		}
	}
	return ans;
}
int main(){
    ios::sync_with_stdio(false);
    int n, m, o; cin >> k >> n >> m >> o;
    int B = (n-1)/k+1;
    piece g[B][19];
    FOR(i, 0, B){
    	FOR(j, 0, 19) g[i][j].init();
	}
	FOR(i, 0, m){
		int a, b, t; cin >> a >> b >> t;
		g[a/k][0].upd(a%k, b%k, t); 
	}
	FOR(i, 1, 19){
		FOR(j, 0, B-(1<<i)){
			g[j][i] = comb(g[j][i-1], g[j+(1<<(i-1))][i-1]);
		}
	}
	while (o--){
		int a, b; cin >> a >> b;
		piece ans; ans.init();
		int found = -1;
		int len = b/k - a/k;
		int cnt = 0; int pos = a/k;
		while (len > 0){
			if (len % 2 == 1){
				if (found == -1){
					ans = g[pos][cnt]; found = 1;
				}
				else ans = comb(ans, g[pos][cnt]);
				pos += (1<<cnt);
			}
			len /= 2;
			cnt++;
		}
		cout << ans.dist[a%k][b%k] << '\n';
	}
}

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