oj.uz

Submission #714518

# Submission time Handle Problem Language Result Execution time Memory
714518 2023-03-24T21:22:50 Z lukameladze Toll (BOI17_toll) C++14
49 / 100
 1961 ms 22740 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
// #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 2e5 + 5, inf = 1e9;
int t,n,k,a[N], m, q, x;
vector <vector <int> > tree[N], zer_vii;
vector <vector <int> > merge(vector <vector <int> > a, vector <vector <int> > b) {
	vector <vector <int> > res;
	res  = vector < vector <int> > (k, vector <int> (k, inf));
	zer_vii = vector < vector <int> > (k, vector <int> (k, inf));
	for (int i = 0; i < k; i++) zer_vii[i][i] = 0;
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++) {
			for (int m = 0; m < k; m++) {
				res[i][j] = min(res[i][j], a[i][m] + b[m][j]);
			}
		}
	}
	return res;
}
void build(int node, int le, int ri) {
	tree[node] = vector < vector <int> > (k, vector <int> (k, inf));
	if (le == ri) {
		return ;
	}
	int mid = (le + ri) / 2;
	build(2 * node, le, mid);
	build(2 * node + 1, mid + 1, ri);
}
void update(int node, int le, int ri, int idxa, int rema, int idxb, int remb, int val) {
	if (le > idxa || ri < idxa) return ;
	if (le == ri) {
		tree[node][rema][remb] = min(tree[node][rema][remb], val);
		return ;
	}
	int mid = (le + ri) / 2;
	update(2 * node, le, mid, idxa, rema, idxb, remb, val);
	update(2 * node + 1, mid + 1, ri, idxa, rema, idxb, remb, val);
	tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
vector <vector <int> > getans(int node, int le, int ri, int start, int end) {
	if (le > end || ri < start) return zer_vii;
	if (le >= start && ri <= end) {
		return tree[node];	
	}
	int mid = (le + ri) / 2;
	vector <vector <int> > p1, p2, res;
	p1 = getans(2 * node, le, mid, start, end); p2 = getans(2 * node + 1, mid + 1, ri, start, end);
	res = merge(p1, p2);
	return res;
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>k>>n>>m>>q;
	build(1, 0, (n - 1) / k);
	for (int i = 1; i <= m; i++) {
		int a, b, x;
		cin>>a>>b>>x;
		update(1, 0, (n - 1) / k, a / k, a % k, b / k, b % k, x);
	}
	while (q--) {
		int a, b;
		cin>>a>>b;
		vector <vector <int> > ans;
		ans = getans(1, 0, (n - 1) / k, a / k, b / k - 1);
		cout<<(ans[a % k][b % k] < inf ? ans[a % k][b % k] : -1)<<"\n";
	}	
}

Compilation message

toll.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main() {
      | ^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 12280 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 12 ms 5164 KB Output is correct
6 Correct 13 ms 5168 KB Output is correct
7 Correct 12 ms 5076 KB Output is correct
8 Correct 375 ms 12232 KB Output is correct
9 Correct 398 ms 12256 KB Output is correct
10 Runtime error 21 ms 22740 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 12920 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 47 ms 5236 KB Output is correct
8 Correct 50 ms 5264 KB Output is correct
9 Correct 327 ms 12236 KB Output is correct
10 Correct 1326 ms 13160 KB Output is correct
11 Correct 729 ms 12960 KB Output is correct
12 Correct 757 ms 12140 KB Output is correct
13 Correct 1961 ms 11056 KB Output is correct
14 Correct 765 ms 9848 KB Output is correct
15 Correct 1025 ms 9648 KB Output is correct
16 Correct 1014 ms 9608 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 7 ms 5164 KB Output is correct
7 Correct 10 ms 5076 KB Output is correct
8 Correct 39 ms 5176 KB Output is correct
9 Correct 28 ms 5076 KB Output is correct
10 Correct 284 ms 12032 KB Output is correct
11 Correct 641 ms 12792 KB Output is correct
12 Correct 1213 ms 12912 KB Output is correct
13 Correct 1314 ms 13136 KB Output is correct
14 Correct 1025 ms 12524 KB Output is correct
15 Correct 964 ms 9520 KB Output is correct
16 Correct 968 ms 9592 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 7 ms 5164 KB Output is correct
7 Correct 10 ms 5076 KB Output is correct
8 Correct 39 ms 5176 KB Output is correct
9 Correct 28 ms 5076 KB Output is correct
10 Correct 284 ms 12032 KB Output is correct
11 Correct 641 ms 12792 KB Output is correct
12 Correct 1213 ms 12912 KB Output is correct
13 Correct 1314 ms 13136 KB Output is correct
14 Correct 1025 ms 12524 KB Output is correct
15 Correct 964 ms 9520 KB Output is correct
16 Correct 968 ms 9592 KB Output is correct
17 Correct 670 ms 12992 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 23 ms 5188 KB Output is correct
24 Correct 30 ms 5208 KB Output is correct
25 Correct 74 ms 5204 KB Output is correct
26 Correct 56 ms 5168 KB Output is correct
27 Correct 297 ms 12028 KB Output is correct
28 Correct 1339 ms 13004 KB Output is correct
29 Correct 1375 ms 13296 KB Output is correct
30 Correct 1039 ms 12652 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 12280 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 12 ms 5164 KB Output is correct
6 Correct 13 ms 5168 KB Output is correct
7 Correct 12 ms 5076 KB Output is correct
8 Correct 375 ms 12232 KB Output is correct
9 Correct 398 ms 12256 KB Output is correct
10 Runtime error 21 ms 22740 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -