oj.uz

Submission #365629

# Submission time Handle Problem Language Result Execution time Memory
365629 2021-02-12T03:19:42 Z luciocf Toll (BOI17_toll) C++14
0 / 100
 193 ms 8300 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 5e4+10;
const ll inf = 1e18+10;

struct Query
{
	int block, a, b, ind;
};

int n, k;

ll ans[maxn];

ll dist[2][maxn];

vector<pii> grafo[2][maxn];
vector<Query> qry[maxn];

void calc_dist(int s, int q, int l, int r)
{
	for (int i = l; i <= r; i++)
		dist[q][i] = inf;

	dist[q][s] = 0;

	queue<int> fila;
	fila.push(s);

	while (!fila.empty())
	{
		int u = fila.front(); fila.pop();

		for (auto pp: grafo[q][u])
		{
			int v = pp.ff, w = pp.ss;

			if (v >= l && v <= r && dist[q][v] > dist[q][u] + 1ll*w)
			{
				dist[q][v] = dist[q][u] + 1ll*w;
				fila.push(v);
			}
		}
	}
}

void solve(int l, int r)
{
	if (l > r) return;

	int mid = (l+r)>>1;

	for (int u = k*mid; u < min(n, k*(mid+1)); u++)
	{
		calc_dist(u, 0, k*l, min(n-1, k*(r+1)-1)); calc_dist(u, 1,  k*l, min(n-1, k*(r+1)-1));

		for (int i = l; i <= r; i++)
		{
			for (auto Q: qry[i])
			{
				if (Q.block < mid) continue;
				if (Q.block > r) break;

				int a = Q.a, b = Q.b, ind = Q.ind;

				ans[ind] = min(ans[ind], dist[1][a] + dist[0][b]);
			}
		}
	}

	solve(l, mid-1); solve(mid+1, r);
}

int main(void)
{
	int m, q;
	scanf("%d %d %d %d", &k, &n, &m, &q);

	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);

		grafo[0][u].push_back({v, w});
		grafo[1][v].push_back({u, w});
	}

	for (int i = 1; i <= q; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);

		qry[a/k].push_back({b/k, a, b, i});
		ans[i] = inf;
	}

	solve(0, (n-1)/k);

	for (int i = 1; i <= q; i++)
	{
		if (ans[i] == inf) printf("-1\n");
		else printf("%lld\n", ans[i]);
	}
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  scanf("%d %d %d %d", &k, &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |   scanf("%d %d %d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 8300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 8292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 8300 KB Output isn't correct
2 Halted 0 ms 0 KB -