oj.uz

Submission #667148

# Submission time Handle Problem Language Result Execution time Memory
667148 2022-11-30T13:08:28 Z flappybird Toll (BOI17_toll) C++17
7 / 100
 1189 ms 524288 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 17
#define INF 10000000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MK 5
vector<vector<ll>> sp[MAX][MAXS];
int K;
vector<vector<ll>> operator+(vector<vector<ll>>& v1, vector<vector<ll>>& v2) {
	vector<vector<ll>> res = vector<vector<ll>>(K, vector<ll>(K, INF));
	int i, j, k;
	for (i = 0; i < K; i++) for (j = 0; j < K; j++) for (k = 0; k < K; k++) res[i][j] = min(res[i][j], v1[i][k] + v2[k][j]);
	return res;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, Q;
	cin >> K >> N >> M >> Q;
	int i, j, k, l;
	int X = (N + K - 1) / K;
	for (i = 0; i < MAX; i++) for (j = 0; j < MAXS; j++) sp[i][j] = vector<vector<ll>>(K, vector<ll>(K, INF));
	int a, b, c;
	for (i = 1; i <= M; i++) {
		cin >> a >> b >> c;
		sp[a / K][0][a % K][b % K] = c;
	}
	for (j = 1; j < MAXS; j++) for (i = 0; i <= X; i++) sp[i][j] = sp[i][j - 1] + sp[i + (1 << j - 1)][j - 1];
	while (Q--) {
		cin >> a >> b;
		int aa = a;
		int d = b / K - a / K;
		a /= K;
		vector<vector<ll>> v;
		for (i = 0; i < MAXS; i++) {
			if (d >> i & 1) {
				if (v.empty()) v = sp[a][i];
				else v = v + sp[a][i];
				a += 1 << i;
			}
		}
		ll ans = v[aa % K][b % K];
		if (ans >= INF) cout << -1 << ln;
		else cout << ans << ln;
	}
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:38:95: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   38 |  for (j = 1; j < MAXS; j++) for (i = 0; i <= X; i++) sp[i][j] = sp[i][j - 1] + sp[i + (1 << j - 1)][j - 1];
      |                                                                                             ~~^~~
toll.cpp:30:12: warning: unused variable 'k' [-Wunused-variable]
   30 |  int i, j, k, l;
      |            ^
toll.cpp:30:15: warning: unused variable 'l' [-Wunused-variable]
   30 |  int i, j, k, l;
      |               ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 294820 KB Output is correct
2 Correct 422 ms 294540 KB Output is correct
3 Correct 392 ms 294544 KB Output is correct
4 Correct 391 ms 294468 KB Output is correct
5 Correct 417 ms 294564 KB Output is correct
6 Correct 438 ms 294608 KB Output is correct
7 Correct 429 ms 294488 KB Output is correct
8 Correct 693 ms 294860 KB Output is correct
9 Correct 595 ms 294824 KB Output is correct
10 Correct 609 ms 294668 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 508792 KB Output is correct
2 Correct 476 ms 294544 KB Output is correct
3 Runtime error 1189 ms 524288 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 294448 KB Output is correct
2 Runtime error 1189 ms 524288 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 294448 KB Output is correct
2 Runtime error 1189 ms 524288 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 294820 KB Output is correct
2 Correct 422 ms 294540 KB Output is correct
3 Correct 392 ms 294544 KB Output is correct
4 Correct 391 ms 294468 KB Output is correct
5 Correct 417 ms 294564 KB Output is correct
6 Correct 438 ms 294608 KB Output is correct
7 Correct 429 ms 294488 KB Output is correct
8 Correct 693 ms 294860 KB Output is correct
9 Correct 595 ms 294824 KB Output is correct
10 Correct 609 ms 294668 KB Output is correct
11 Correct 849 ms 508792 KB Output is correct
12 Correct 476 ms 294544 KB Output is correct
13 Runtime error 1189 ms 524288 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -