oj.uz

Submission #714561

# Submission time Handle Problem Language Result Execution time Memory
714561 2023-03-25T05:23:05 Z parsadox2 Toll (BOI17_toll) C++14
0 / 100
 47 ms 9140 KB 
#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 5e4 + 10 , maxsq = 100 , maxk = 7 , inf = 1e9;
int n , m , q , k , dis[maxn] , dis_jmp[maxn][maxk];
vector <pair<int , int>> adj[maxn];
vector <int> vec;

void Relax()
{
	for(auto u : vec)   dis[u] = inf;
	vec.clear();
}

void find_nex(int now , int to)
{
	int l = now * k , r = min(n , l + k);
	for(int i = l ; i < r ; i++)  vec.pb(i);
	if(now == to)  return;
	for(int i = l ; i < r ; i++)
		for(auto u : adj[i])
			dis[u.F] = min(dis[u.F] , dis[i] + u.S);
	find_nex(now + 1 , to);
}

void Build(int num)
{
	int l = num * k , r = min(n , l + k);
	int l2 = (num + maxsq) * k;
	for(int i = l ; i < r ; i++)
	{
		dis[i] = 0;
		find_nex(num , num + maxsq);
		for(int j = 0 ; j < k ; j++)
			dis_jmp[i][j] = dis[l2 + j];
		Relax();
	}
}

void jmp_nex(int a , int b)
{
	int l = a * maxsq , r = min(n , l + k) , l2 = b * maxsq;
	for(int i = l ; i < r ; i++)  vec.pb(i);
	if(a == b)  return;
	for(int i = l ; i < r ; i++)
		for(int j = 0 ; j < k ; j++)
			dis[l2 + j] = min(dis[l2 + j] , dis[i] + dis_jmp[i][j]);
	jmp_nex(a + maxsq , b);
}

void Find_dis(int a , int b)
{
	int tmp = (a + maxsq) / maxsq;
	tmp *= maxsq;
	if(b <= tmp)
	{
		find_nex(a , b);
		return;
	}
	find_nex(a , tmp);
	int tmp2 = b / maxsq;
	tmp2 *= maxsq;
	jmp_nex(tmp , tmp2);
	find_nex(tmp2 , b);
}

int32_t main()
{
	fast;
	cin >> k >> n >> m >> q;
	for(int i = 0 ; i < n ; i++)  dis[i] = inf;
	for(int i = 0 ; i < m ; i++)
	{
		int v , u , c;  cin >> v >> u >> c;
		adj[v].pb({u , c});
	}
	for(int i = 0 ; (i + maxsq) * k < n ; i += maxsq)  Build(i);
	while(q--)
	{
		int v , u;  cin >> v >> u;
		if(v > u)
		{
			cout << -1 << '\n';
			continue;
		}
		dis[v] = 0;
		vec.pb(v);
		Find_dis(v / k , u / k);
		cout << (dis[u] == inf ? -1 : dis[u]) << '\n';
		Relax();
	}
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 9140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 8360 KB Execution killed with signal 11
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 Incorrect 2 ms 1492 KB Output isn't correct
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 Incorrect 2 ms 1492 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 9140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -