oj.uz

Submission #714642

# Submission time Handle Problem Language Result Execution time Memory
714642 2023-03-25T07:10:08 Z parsadox2 Toll (BOI17_toll) C++14
100 / 100
 197 ms 27852 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 , maxl = 17 , maxk = 7 , inf = 1e9;
int n, m , q , k , dis[maxn][maxl][maxk];
vector <pair<int , int>> adj[maxn];

int find_nex(int v , int jmp , int ps)
{
	int now = v / k;
	int to = now + (1 << jmp);
	to *= k;
	to += ps;
	return min(to , n);
}

int Find_ans(int nb , int np , int fb , int fp)
{
	int res[2][maxk];
	for(int i = 0 ; i < k ; i++)  res[0][i] = res[1][i] = inf;
	res[0][np] = 0;
	int l = nb * k , fbi = (fb - nb) , upd = 0 , val = fb - nb;
	for(int jmp = 0 ; jmp < maxl ; jmp++)  if((val >> jmp) & 1)
	{
		for(int i = 0 ; i < k ; i++)  res[upd ^ 1][i] = inf;
		
		for(int from = 0 ; from < k ; from++)
		{
			int v = l + from;
			for(int to = 0 ; to < k ; to++)
			{
				res[upd ^ 1][to] = min(res[upd ^ 1][to] , res[upd][from] + dis[v][jmp][to]);
			}
		}
		nb += (1 << jmp);
		l = nb * k;
		upd ^= 1;
	}
	return (res[upd][fp] == inf ? -1 : res[upd][fp]);
}

int32_t main()
{
	fast;
	cin >> k >> n >> m >> q;
	for(int i = 0 ; i < maxn ; i++)
		for(int j = 0 ; j < maxl ; j++)
			for(int k = 0 ; k < maxk ; k++)
				dis[i][j][k] = inf;

	for(int i = 0 ; i < m ; i++)
	{
		int v , u , c;  cin >> v >> u >> c;
		adj[v].pb({u , c});
		dis[v][0][(u % k)] = c;
	}
	for(int jmp = 1 ; jmp < maxl ; jmp++)
		for(int v = 0 ; v < n ; v++)
			for(int from = 0 ; from < k ; from++)
				for(int to = 0 ; to < k ; to++)  
					dis[v][jmp][to] = min(dis[v][jmp][to] , dis[v][jmp - 1][from] + dis[find_nex(v , jmp - 1 , from)][jmp - 1][to]);
	while(q--)
	{
		int v , u;  cin >> v >> u;
		if(v / k >= u / k)
		{
			cout << -1 << '\n';
			continue;
		}
		cout << Find_ans(v / k , v % k , u / k , u % k) << '\n';
	}
	return 0;

}

Compilation message

toll.cpp: In function 'int Find_ans(int, int, int, int)':
toll.cpp:31:19: warning: unused variable 'fbi' [-Wunused-variable]
   31 |  int l = nb * k , fbi = (fb - nb) , upd = 0 , val = fb - nb;
      |                   ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 26756 KB Output is correct
2 Correct 12 ms 24736 KB Output is correct
3 Correct 15 ms 24760 KB Output is correct
4 Correct 14 ms 24848 KB Output is correct
5 Correct 13 ms 24820 KB Output is correct
6 Correct 13 ms 24776 KB Output is correct
7 Correct 13 ms 24788 KB Output is correct
8 Correct 52 ms 26660 KB Output is correct
9 Correct 49 ms 26596 KB Output is correct
10 Correct 37 ms 24896 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 26632 KB Output is correct
2 Correct 12 ms 24788 KB Output is correct
3 Correct 13 ms 24736 KB Output is correct
4 Correct 12 ms 24788 KB Output is correct
5 Correct 11 ms 24664 KB Output is correct
6 Correct 11 ms 24676 KB Output is correct
7 Correct 14 ms 24908 KB Output is correct
8 Correct 17 ms 24944 KB Output is correct
9 Correct 55 ms 26676 KB Output is correct
10 Correct 108 ms 27596 KB Output is correct
11 Correct 75 ms 26688 KB Output is correct
12 Correct 106 ms 26580 KB Output is correct
13 Correct 137 ms 27852 KB Output is correct
14 Correct 71 ms 26808 KB Output is correct
15 Correct 76 ms 26444 KB Output is correct
16 Correct 71 ms 26324 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24652 KB Output is correct
2 Correct 12 ms 24788 KB Output is correct
3 Correct 15 ms 24788 KB Output is correct
4 Correct 14 ms 24680 KB Output is correct
5 Correct 15 ms 24788 KB Output is correct
6 Correct 16 ms 24788 KB Output is correct
7 Correct 16 ms 24812 KB Output is correct
8 Correct 15 ms 24896 KB Output is correct
9 Correct 16 ms 24856 KB Output is correct
10 Correct 62 ms 26676 KB Output is correct
11 Correct 76 ms 26700 KB Output is correct
12 Correct 101 ms 27480 KB Output is correct
13 Correct 117 ms 27844 KB Output is correct
14 Correct 92 ms 27144 KB Output is correct
15 Correct 96 ms 26416 KB Output is correct
16 Correct 84 ms 26416 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24652 KB Output is correct
2 Correct 12 ms 24788 KB Output is correct
3 Correct 15 ms 24788 KB Output is correct
4 Correct 14 ms 24680 KB Output is correct
5 Correct 15 ms 24788 KB Output is correct
6 Correct 16 ms 24788 KB Output is correct
7 Correct 16 ms 24812 KB Output is correct
8 Correct 15 ms 24896 KB Output is correct
9 Correct 16 ms 24856 KB Output is correct
10 Correct 62 ms 26676 KB Output is correct
11 Correct 76 ms 26700 KB Output is correct
12 Correct 101 ms 27480 KB Output is correct
13 Correct 117 ms 27844 KB Output is correct
14 Correct 92 ms 27144 KB Output is correct
15 Correct 96 ms 26416 KB Output is correct
16 Correct 84 ms 26416 KB Output is correct
17 Correct 75 ms 26592 KB Output is correct
18 Correct 13 ms 24732 KB Output is correct
19 Correct 12 ms 24788 KB Output is correct
20 Correct 11 ms 24788 KB Output is correct
21 Correct 14 ms 24704 KB Output is correct
22 Correct 14 ms 24784 KB Output is correct
23 Correct 16 ms 24876 KB Output is correct
24 Correct 13 ms 24788 KB Output is correct
25 Correct 15 ms 24916 KB Output is correct
26 Correct 16 ms 24912 KB Output is correct
27 Correct 52 ms 26572 KB Output is correct
28 Correct 112 ms 27584 KB Output is correct
29 Correct 124 ms 27844 KB Output is correct
30 Correct 133 ms 27212 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 26756 KB Output is correct
2 Correct 12 ms 24736 KB Output is correct
3 Correct 15 ms 24760 KB Output is correct
4 Correct 14 ms 24848 KB Output is correct
5 Correct 13 ms 24820 KB Output is correct
6 Correct 13 ms 24776 KB Output is correct
7 Correct 13 ms 24788 KB Output is correct
8 Correct 52 ms 26660 KB Output is correct
9 Correct 49 ms 26596 KB Output is correct
10 Correct 37 ms 24896 KB Output is correct
11 Correct 82 ms 26632 KB Output is correct
12 Correct 12 ms 24788 KB Output is correct
13 Correct 13 ms 24736 KB Output is correct
14 Correct 12 ms 24788 KB Output is correct
15 Correct 11 ms 24664 KB Output is correct
16 Correct 11 ms 24676 KB Output is correct
17 Correct 14 ms 24908 KB Output is correct
18 Correct 17 ms 24944 KB Output is correct
19 Correct 55 ms 26676 KB Output is correct
20 Correct 108 ms 27596 KB Output is correct
21 Correct 75 ms 26688 KB Output is correct
22 Correct 106 ms 26580 KB Output is correct
23 Correct 137 ms 27852 KB Output is correct
24 Correct 71 ms 26808 KB Output is correct
25 Correct 76 ms 26444 KB Output is correct
26 Correct 71 ms 26324 KB Output is correct
27 Correct 13 ms 24652 KB Output is correct
28 Correct 12 ms 24788 KB Output is correct
29 Correct 15 ms 24788 KB Output is correct
30 Correct 14 ms 24680 KB Output is correct
31 Correct 15 ms 24788 KB Output is correct
32 Correct 16 ms 24788 KB Output is correct
33 Correct 16 ms 24812 KB Output is correct
34 Correct 15 ms 24896 KB Output is correct
35 Correct 16 ms 24856 KB Output is correct
36 Correct 62 ms 26676 KB Output is correct
37 Correct 76 ms 26700 KB Output is correct
38 Correct 101 ms 27480 KB Output is correct
39 Correct 117 ms 27844 KB Output is correct
40 Correct 92 ms 27144 KB Output is correct
41 Correct 96 ms 26416 KB Output is correct
42 Correct 84 ms 26416 KB Output is correct
43 Correct 75 ms 26592 KB Output is correct
44 Correct 13 ms 24732 KB Output is correct
45 Correct 12 ms 24788 KB Output is correct
46 Correct 11 ms 24788 KB Output is correct
47 Correct 14 ms 24704 KB Output is correct
48 Correct 14 ms 24784 KB Output is correct
49 Correct 16 ms 24876 KB Output is correct
50 Correct 13 ms 24788 KB Output is correct
51 Correct 15 ms 24916 KB Output is correct
52 Correct 16 ms 24912 KB Output is correct
53 Correct 52 ms 26572 KB Output is correct
54 Correct 112 ms 27584 KB Output is correct
55 Correct 124 ms 27844 KB Output is correct
56 Correct 133 ms 27212 KB Output is correct
57 Correct 197 ms 27848 KB Output is correct
58 Correct 65 ms 26644 KB Output is correct
59 Correct 99 ms 26756 KB Output is correct