Submission #838947

#	Time	Username	Problem	Language	Result	Execution time	Memory
838947		danitro	Toll (BOI17_toll)	C++14	7 / 100	3071 ms	220112 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define MAX 51000

int k, n, m, q, a, b, c, dist[5][MAX], ans[MAX];

struct Query
{
	int u, v, l, r, idx;
};

vector<Query> t;

vector<pair<int, int> > gr[MAX];

void find_dist(int ost, int l, int r, int p)
{
	dist[ost][k * l + ost] = 0;
	queue<int> q;
	q.push(k * l + ost);
	int node;
	
	while(!q.empty())
	{
		node = q.front();
		q.pop();
		if(node / k == r)continue;
		for(int i = 0; i < gr[node].size(); i++)
		{
			//if(gr[node][i].first / k > max(l, r) + 1 || gr[node][i].first / k < min(l, r) - 1)continue;
			if(node / k == gr[node][i].first / k + p)
			{
				q.push(gr[node][i].first);
				dist[ost][gr[node][i].first] = min(dist[ost][gr[node][i].first], 
												   dist[ost][node] + gr[node][i].second);
			}
		}
	}
	return;
}

void solve(int l, int r, vector<Query>& t)
{
	if(l >= r || t.size() == 0)return;
	int mid = (l + r) / 2;
	
	for(int i = 0; i < 5; i++)fill(dist[i] + l * k, dist[i] + r * k + k, INT_MAX / 3);
	
	for(int i = 0; i < k; i++)find_dist(i, mid, r, -1);
	for(int i = 0; i < k; i++)find_dist(i, mid, l, 1);
	
	vector<Query> todo[2];
	for(auto q : t)
	{
		if(q.l <= mid && mid <= q.r)
		{
			for(int j = 0; j < k; j++)
			{
				ans[q.idx] = min(ans[q.idx], dist[j][q.u] + dist[j][q.v]);
			}
		}
		else todo[q.l > mid].push_back(q);
	}
	
	solve(l, mid - 1, todo[0]);
	solve(mid + 1, r, todo[1]);
	
	return ;
}

int main()
{
	scanf("%d%d%d%d", &k, &n, &m, &q);
	
	for(int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		gr[a].push_back({b, c});
		gr[b].push_back({a, c});
	}
	
	t.resize(q);
	for(int i = 0; i < q; i++)
	{
		scanf("%d%d", &t[i].u, &t[i].v);
		t[i].l = t[i].u / k;
		t[i].r = t[i].v / k;
		t[i].idx = i;
	}
	
	fill(ans, ans + q, INT_MAX / 2);
	solve(0, n / k, t);
	
	for(int i = 0; i < q; i++)
	{
		if(ans[i] > INT_MAX / 5)printf("-1\n");
		else printf("%d\n", ans[i]);
	}
	
	return 0;
}

/*

5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13


1 8 7 1
0 1 10
1 2 1
2 3 6
3 4 4
4 5 4
5 6 3
6 7 2
2 3

*/

Compilation message (stderr)

toll.cpp: In function 'void find_dist(int, int, int, int)':
toll.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i = 0; i < gr[node].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d%d%d%d", &k, &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d%d%d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d%d", &t[i].u, &t[i].v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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