Submission #835868

#	Time	Username	Problem	Language	Result	Execution time	Memory
835868		samek08	Toll (BOI17_toll)	C++14	0 / 100	3080 ms	10020 KiB

toll

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a,b) for (int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()

struct Krawedz
{
	int v, cena;
};

struct Zapytanie
{
	int a, b, idx;
};

const int max_N = 5e4+5, max_K = 5, max_Q = 1e4+5;
const ll INF = 1e18+20;
int k = 0, n = 0, m = 0, q = 0, a = 0, b = 0, c = 0;
ll wyn[max_Q];
vector<Krawedz> krawedzie[max_N];
vector<Krawedz> odwrocone_krawedzie[max_N];
vector<Zapytanie> zap;
ll dist[max_K][max_N];

inline void dziel_i_rzadz(int l, int p, vector<Zapytanie> zap)
{
	if (l == p) return;
	int s = (l+p) / 2;
	vector<Zapytanie> lewe, prawe, akt;
	for (auto x : zap)
	{
		if (x.b/k < s) lewe.pb(x);
		else if (x.a/k > s) prawe.pb(x);
		else akt.pb(x);
	}
	rep(i,max_K)
	{
		rep(j,max_K) for (int f = l*k; f <= (p+1)*k; ++f) dist[j][f] = INF;
		dist[i][s*k+i] = 0;
		for (int j = s*k-1; j >= 0; --j) for (auto x : krawedzie[j]) dist[i][j] = min(dist[i][j],dist[i][x.v] + x.cena);
		for (int j = (s+1)*k; j < n; ++j) for (auto x : odwrocone_krawedzie[j]) dist[i][j] = min(dist[i][j],dist[i][x.v] + x.cena);
		for (auto x : akt) if (dist[i][x.a] != INF and dist[i][x.b] != INF) wyn[x.idx] = min(wyn[x.idx],dist[i][x.a] + dist[i][x.b]);
	}
	dziel_i_rzadz(l,s,lewe), dziel_i_rzadz(s+1,p,prawe);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> k >> n >> m >> q;
	rep(i,m)
	{
		cin >> a >> b >> c;
		krawedzie[a].pb({b,c}), odwrocone_krawedzie[b].pb({a,c});
	}
	rep(i,q)
	{
		cin >> a >> b;
		if (a > b) swap(a,b);
		zap.pb({a,b,i});
	}
	rep(i,max_Q) wyn[i] = INF;
	dziel_i_rzadz(0,n/k,zap);
	rep(i,q)
	{
		if(wyn[i] == INF) cout << "-1" << '\n';
		else cout << wyn[i] << '\n';
	}
	return 0;
}

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