Submission #162997

#	Time	Username	Problem	Language	Result	Execution time	Memory
162997		Minnakhmetov	Toll (BOI17_toll)	C++14	100 / 100	141 ms	19064 KiB

toll

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

const int N = 5e5 + 5, K = 5, INF = 6e8;
int w[N][K][K];
int n, m, k, o;

struct Node {
	int w[K][K];

	void fill(int val) {
		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				w[i][j] = val;
			}
		}
	}
} t[N * 4];



Node mrg(Node a, Node b, int w[K][K]) {
	Node res;
	res.fill(INF);

	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++) {
			for (int x = 0; x < k; x++) {
				for (int y = 0; y < k; y++) {
					res.w[i][y] = min(res.w[i][y], a.w[i][j] + w[j][x] + b.w[x][y]);
				}
			}
		}
	}

	// for (int i = 0; i < k; i++) {
	// 	for (int j = 0; j < k; j++) {
	// 		cout << i << " " << j << " " << a.w[i][j] << "\n";
	// 	}
	// }
	// cout << "\n";

	// for (int i = 0; i < k; i++) {
	// 	for (int j = 0; j < k; j++) {
	// 		cout << i << " " << j << " " << b.w[i][j] << "\n";
	// 	}
	// }
	// cout << "\n";

	// for (int i = 0; i < k; i++) {
	// 	for (int j = 0; j < k; j++) {
	// 		cout << i << " " << j << " " << res.w[i][j] << "\n";
	// 	}
	// }
	// cout << "\n";

	// for (int i = 0; i < k; i++) {
	// 	for (int j = 0; j < k; j++) {
	// 		cout << i << " " << j << " " << w[i][j] << "\n";
	// 	}
	// }
	// cout << "\n";
	// cout << "\n";


	return res;
}

void build(int v, int L, int R) {
	if (L == R) {
		t[v].fill(INF);
		for (int i = 0; i < k; i++)
			t[v].w[i][i] = 0;
	}
	else {
		int m = (L + R) >> 1;
		build(v * 2, L, m);
		build(v * 2 + 1, m + 1, R);
		t[v] = mrg(t[v * 2], t[v * 2 + 1], w[m]);
	}
}

Node que(int l, int r, int v, int L, int R) {
	if (l == L && r == R)
		return t[v];

	int m = (L + R) >> 1;
	if (r <= m)
		return que(l, min(m, r), v * 2, L, m);
	if (l > m)
		return que(max(m + 1, l), r, v * 2 + 1, m + 1, R);

	return mrg(que(l, min(m, r), v * 2, L, m),
		que(max(m + 1, l), r, v * 2 + 1, m + 1, R), w[m]);
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> k >> n >> m >> o;

    int ctb = (n - 1) / k + 1;

    for (int i = 0; i < ctb; i++) {
    	for (int x = 0; x < k; x++) {
    		for (int y = 0; y < k; y++) {
    			w[i][x][y] = INF;
    		}
    	}
    }

    for (int i = 0; i < m; i++) {
    	int a, b, c;
    	cin >> a >> b >> c;

    	int p = a / k;
    	a %= k;
    	b %= k;

    	w[p][a][b] = min(w[p][a][b], c);

    	// cout << p << " " << a << " " << b << " " << c << "\n";
    }



    build(1, 0, ctb - 1);

    for (int i = 0; i < o; i++) {
    	int a, b;
    	cin >> a >> b;

    	int x = a / k,
    		y = b / k;

    	if (x == y) {
    		cout << "-1\n";
    	}
    	else {
    		Node res = que(x, y, 1, 0, ctb - 1);

    		int ans = res.w[a % k][b % k];
    		cout << (ans < INF ? ans : -1) << "\n";

    		// for (int i = 0; i < k; i++) {
    		// 	for (int j = 0; j < k; j++) {
    		// 		cout << i << " " << j << " " << res.w[i][j] << "\n";
    		// 	}
    		// }
    	}
    }



    return 0;
}

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