oj.uz

Submission #835868

# Submission time Handle Problem Language Result Execution time Memory
835868 2023-08-23T21:31:29 Z samek08 Toll (BOI17_toll) C++14
0 / 100
 3000 ms 10020 KB 
#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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 1 ms 2684 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 17 ms 2892 KB Output is correct
7 Correct 9 ms 2900 KB Output is correct
8 Correct 10 ms 3076 KB Output is correct
9 Correct 9 ms 2900 KB Output is correct
10 Execution timed out 3045 ms 8584 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 1 ms 2684 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 17 ms 2892 KB Output is correct
7 Correct 9 ms 2900 KB Output is correct
8 Correct 10 ms 3076 KB Output is correct
9 Correct 9 ms 2900 KB Output is correct
10 Execution timed out 3045 ms 8584 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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