Submission #754388

#	Time	Username	Problem	Language	Result	Execution time	Memory
754388		Markomafko972	Toll (BOI17_toll)	C++14	100 / 100	961 ms	127172 KiB

toll

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int k, n, ed, q, a, b, c;
vector<pii> v[50005];
vector<pii> rev[50005];
vector<int> br[50005];
map<int, int> m[50005];
map<int, int> bio[50005];

void rek(int l, int r) {
	if (l >= r) return;
	
	
	int mid = (l+r)/2;
	for (int i = mid-1; i >= l; i--) {
		for (int j = 0; j < br[mid].size(); j++) {
			int poc = br[mid][j];
			for (int w = 0; w < br[i+1].size(); w++) {
				int cvor = br[i+1][w];
				if (m[cvor][poc] == 0 && cvor != poc) continue;
				
				for (int slj = 0; slj < rev[cvor].size(); slj++) {
					int sus = rev[cvor][slj].X;
					int dist = m[cvor][poc]+rev[cvor][slj].Y;
					if (m[sus][poc] == 0 || m[sus][poc] > dist) m[sus][poc] = dist;
				}
			}
		}
	}
	for (int i = mid+2; i <= r; i++) {
		for (int j = 0; j < br[mid+1].size(); j++) {
			int poc = br[mid+1][j];
			for (int w = 0; w < br[i-1].size(); w++) {
				int cvor = br[i-1][w];
				if (m[poc][cvor] == 0 && cvor != poc) continue;
			
				for (int slj = 0; slj < v[cvor].size(); slj++) {
					int sus = v[cvor][slj].X;
					int dist = m[poc][cvor]+v[cvor][slj].Y;
					if (m[poc][sus] == 0 || m[poc][sus] > dist) m[poc][sus] = dist;
				}
			}
		}
	}
	
	rek(l, mid);
	rek(mid+1, r);
}

int trazimid(int l, int r, int lo, int hi) {
	if (hi < l || r < lo) return -1;
	int mid = (lo+hi)/2;
	if (l <= mid && mid <= r) return mid;
		
	return max(trazimid(l, r, lo, mid), trazimid(l, r, mid+1, hi));
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> k >> n >> ed >> q;
	for (int i = 0; i < ed; i++) {
		cin >> a >> b >> c;
		v[a].push_back({b, c});
		rev[b].push_back({a, c});
	}
	for (int i = 0; i < n; i++) br[i/k].push_back(i);
	
	rek(0, (n-1)/k);
	
	for (int i = 0; i < q; i++) {
		cin >> a >> b;
		int sred = trazimid(a/k, b/k, 0, (n-1)/k);
		
		if (sred == b/k) {
			if (m[a][b] == 0) cout << "-1\n";
			else cout << m[a][b] << "\n";
		}
		else {
			int mini = 1e9;
			for (int j = 0; j < br[sred].size(); j++) {
				int cvor1 = br[sred][j];
				for (int w = 0; w < v[cvor1].size(); w++) {
					int cvor2 = v[cvor1][w].X;
					int tez = v[cvor1][w].Y;
					
					if (m[a][cvor1] == 0 && a != cvor1) continue;
					if (m[cvor2][b] == 0 && b != cvor2) continue;
					
					mini = min(mini, m[a][cvor1]+tez+m[cvor2][b]);
				}
			}
			if (mini == 1e9) cout << "-1\n";
			else cout << mini << "\n";
		}
	}

	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'void rek(int, int)':
toll.cpp:26:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for (int j = 0; j < br[mid].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~
toll.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for (int w = 0; w < br[i+1].size(); w++) {
      |                    ~~^~~~~~~~~~~~~~~~
toll.cpp:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int slj = 0; slj < rev[cvor].size(); slj++) {
      |                       ~~~~^~~~~~~~~~~~~~~~~~
toll.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int j = 0; j < br[mid+1].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~
toll.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    for (int w = 0; w < br[i-1].size(); w++) {
      |                    ~~^~~~~~~~~~~~~~~~
toll.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int slj = 0; slj < v[cvor].size(); slj++) {
      |                       ~~~~^~~~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    for (int j = 0; j < br[sred].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~~
toll.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int w = 0; w < v[cvor1].size(); w++) {
      |                     ~~^~~~~~~~~~~~~~~~~

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