oj.uz

Submission #838937

# Submission time Handle Problem Language Result Execution time Memory
838937 2023-08-28T10:01:34 Z danitro Toll (BOI17_toll) C++14
7 / 100
 3000 ms 268740 KB 
#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();
		for(int i = 0; i < gr[node].size(); i++)
		{
			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

toll.cpp: In function 'void find_dist(int, int, int, int)':
toll.cpp:29: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]
   29 |   for(int i = 0; i < gr[node].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d%d%d%d", &k, &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d%d%d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%d", &t[i].u, &t[i].v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 4508 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 34 ms 4528 KB Output is correct
9 Correct 18 ms 4452 KB Output is correct
10 Correct 4 ms 2900 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 244476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Execution timed out 3085 ms 268740 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Execution timed out 3085 ms 268740 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 4508 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 34 ms 4528 KB Output is correct
9 Correct 18 ms 4452 KB Output is correct
10 Correct 4 ms 2900 KB Output is correct
11 Execution timed out 3060 ms 244476 KB Time limit exceeded
12 Halted 0 ms 0 KB -