Submission #365528

#	Time	Username	Problem	Language	Result	Execution time	Memory
365528		LucaDantas	Toll (BOI17_toll)	C++17	0 / 100	48 ms	10860 KiB

toll

#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

constexpr int maxn = 1e5+10, inf = 0x3f3f3f3f;

vector<pair<int,int>> g[maxn], query[maxn];

int K, dist_l[maxn][5], dist_r[maxn][5], next_dist_l[maxn][5], next_dist_r[maxn][5], ans[maxn];

void solve(int l, int r) {
	if(l == r) return;
	int m = (l+r) >> 1;
	solve(l, m); solve(m+1, r);

	for(int x = K*m; x < K*(m+1); x++)
		for(int y = 0; y < K; y++)
			dist_r[x][y] = 0;

	for(int i = K*l; i < K*(m+1); i++) {
		while(query[i].size() && query[i].back().first/K <= r) {
			auto [b, id] = query[i].back(); query[i].pop_back();
			for(int x = K*m; x < K*(m+1); x++)
				ans[id] = min(ans[id], dist_r[i][x-K*m]+dist_l[b][x-K*m]);
		}
	}

	for(int esq = 0; esq < K; esq++) {
		for(int x = K*(m+1); x < K*(r+1); x++) {
			for(int meio = 0; meio < K; meio++)
				next_dist_l[x][esq] = min(next_dist_l[x][esq], dist_l[x][meio]+dist_r[K*l+esq][meio]);
		}
	}
	
	for(int dir = 0; dir < K; dir++) {
		for(int x = K*l; x < K*(m+1); x++) {
			for(int meio = 0; meio < K; meio++)
				next_dist_r[x][dir] = min(next_dist_r[x][dir], dist_r[x][meio]+dist_l[K*r+dir][meio]);
		}
	}

	for(int esq = 0; esq < K; esq++)
		for(int x = K*(m+1); x < K*(r+1); x++)
			dist_l[x][esq] = next_dist_l[x][esq], next_dist_l[x][esq] = inf;
	for(int dir = 0; dir < K; dir++)
		for(int x = K*l; x < K*(m+1); x++)
			dist_r[x][dir] = next_dist_r[x][dir], next_dist_r[x][dir] = inf;
}

int main() {
	int n, m, q; scanf("%d %d %d %d", &K, &n, &m, &q);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < K; j++)
			dist_l[i][j] = next_dist_l[i][j] = dist_r[i][j] = next_dist_r[i][j] = inf;
	for(int i = 0, a, b, c; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		if(a < b) swap(a, b);
		dist_l[a][b%K] = c;
	}
	for(int i = 0; i < q; i++) {
		int a, b; scanf("%d %d", &a, &b);
		query[a].push_back({b, i});
		ans[i] = inf;
	}
	for(int i = 0; i < n; i++)
		sort(query[i].begin(), query[i].end()), reverse(query[i].begin(), query[i].end());
	solve(0, (n-1)/K);
	for(int i = 0; i < q; i++)
		printf("%d\n", ans[i]<inf?ans[i]:-1);
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:53:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  int n, m, q; scanf("%d %d %d %d", &K, &n, &m, &q);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   scanf("%d %d %d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:63:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |   int a, b; scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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