Submission #696781

#	Time	Username	Problem	Language	Result	Execution time	Memory
696781		Futorankusu	Toll (BOI17_toll)	C++14	100 / 100	410 ms	179760 KiB

toll

// #pragma gcc optimize("Ofast")
// #pragma GCC optimization("Ofast")
// #pragma optimize(Ofast)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

/**
 *    author:  tpa1410 - futorankusu
 *    rose, hanni, minji     
**/

#include<bits/stdc++.h>

using namespace std;

#define ll long long
typedef pair<ll, ll> pii;
#define rose() ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define mset(a) memset(a, 0, sizeof(a))
#define endl '\n'



const ll hanni = 1e4, minji = 1e9;

struct Matrix{
	long long int a[5][5];
	Matrix(){
		for(int i = 0; i < 5; i++){
			for (int j = 0; j < 5; j++){
				a[i][j] = minji;
			}
		}
	}
};

Matrix mul(Matrix a, Matrix b){
    Matrix c;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            c.a[i][j] = minji;
            for (int k = 0; k < 5; k++) {
                c.a[i][j] = min(c.a[i][j], a.a[i][k] + b.a[k][j]);
            }
        }
    }
    return c;
}

Matrix up[50005][18];
signed main(){
	int k, n, m, o;
    cin >> k >> n >> m >> o;
    for(int i=1; i<=m; i++) {
    	int u, v, w;
    	cin >> u >> v >> w;
//     	up[j][i]: tầng thứ 2^i bên cạnh tầng j
    	up[u/k][0].a[u%k][v%k] = w;
//     	a[x][y]: x là vị trí của đỉnh u trong tầng u nằm, y tương tự là của v
    }
    for(int i=1; (1 << i) <= n; i++){
    	for(int j=0; j + (1 << i) - 1 <= n; j++){
    		up[j][i] = mul(up[j][i-1], up[j+(1<<(i-1))][i-1]);
    	}
    }
    for(int i = 0; i<o; i++){
    	int a, b;
    	cin >> a >> b;
    	Matrix res;
    	for(int j = 0; j < 5; j++){
    		res.a[j][j] = 0;
    	}
    	if(a == b){
    		cout << 0 << endl;
    		continue;
    	}
    	int div1 = a / k, div2 = b / k;
    	int dist = div2 - div1;
    	for(int j = 16; j >= 0; j--){
    		if(dist & (1 << j)){
    			res = mul(res, up[div1][j]);
    			div1 += (1 << j);
    		}
    	}
    	if(res.a[a % k][b % k] == minji) cout << -1 << endl;
    	else cout << res.a[a % k][b % k] << endl;
    }
}

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