Submission #145163

#	Time	Username	Problem	Language	Result	Execution time	Memory
145163		tincamatei	Toll (BOI17_toll)	C++14	100 / 100	134 ms	28144 KiB

toll

#include <bits/stdc++.h>

using namespace std;

const int INF = 500000001;
const int MAX_N = 50000;

struct Matrix {
	int matr[5][5];

	Matrix() {
		for(int i = 0; i < 5; ++i)
			for(int j = 0; j < 5; ++j)
				matr[i][j] = INF;
	}
};

Matrix mergeMatrices(int k, Matrix a, Matrix b) {
	Matrix rez;
	for(int i = 0; i < k; ++i)
		for(int j = 0; j < k; ++j)
			for(int l = 0; l < k; ++l)
				rez.matr[i][j] = min(rez.matr[i][j], a.matr[i][l] + b.matr[l][j]);
	return rez;
}

Matrix aint[1+4*MAX_N];
Matrix tranz[MAX_N];

void init(int K, int nod = 1, int l = 0, int r = MAX_N - 1) {
	if(l < r) {
		int mid = (l + r) / 2;
		init(K, 2 * nod, l, mid);
		init(K, 2 * nod + 1, mid + 1, r);
		aint[nod] = mergeMatrices(K, aint[2 * nod], aint[2 * nod + 1]);
	} else {
		aint[nod] = tranz[l];
	}
}

Matrix query(int K, int i, int j, int l = 0, int r = MAX_N - 1, int nod = 1) {
	if(i <= l && r <= j) {
		return aint[nod];
	} else {
		int mid = (l + r) / 2;
		Matrix rez;
		if(i <= mid) {
			rez = query(K, i, j, l, mid, 2 * nod);
			if(j > mid)
				rez = mergeMatrices(K, rez, query(K, i, j, mid + 1, r, 2 * nod + 1));
		} else
			rez = query(K, i, j, mid + 1, r, 2 * nod + 1);
		return rez;
	}
}

int main() {
	int K, N, M, O;

	scanf("%d%d%d%d", &K, &N, &M, &O);
	for(int i = 0; i < M; ++i) {
		int a, b, t;
		scanf("%d%d%d", &a, &b, &t);
		tranz[a / K].matr[a % K][b % K] = min(tranz[a / K].matr[a % K][b % K], t);
	}

	init(K);

	for(int i = 0; i < O; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		if(a / K >= b / K)
			printf("-1\n");
		else {
			Matrix rez = query(K, a / K, b / K - 1);
			if(rez.matr[a % K][b % K] >= INF)
				printf("-1\n");
			else
				printf("%d\n", rez.matr[a % K][b % K]);
		}
	}

	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &K, &N, &M, &O);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

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