Submission #365626

#	Time	Username	Problem	Language	Result	Execution time	Memory
365626		luciocf	Toll (BOI17_toll)	C++14	0 / 100	3098 ms	11244 KiB

toll

#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];

bool mark[maxn];
vector<int> ord;

ll dist[2][maxn];

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

void dfs(int u)
{
	mark[u] = 1;

	for (auto pp: grafo[0][u])
		if (!mark[pp.ff])
			dfs(pp.ff);

	ord.push_back(u);
}

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;

	if (q == 1) reverse(ord.begin(), ord.end());

	for (auto u: ord)
		for (auto pp: grafo[q^1][u])
			dist[q][u] = min(dist[q][u], dist[q][pp.ff] + 1ll*pp.ss);

	if (q == 1) reverse(ord.begin(), ord.end());
}

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;
	}

	for (int i = 0; i < n; i++)
		if (!mark[i])
			dfs(i);

	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 (stderr)

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

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