oj.uz

Submission #667150

# Submission time Handle Problem Language Result Execution time Memory
667150 2022-11-30T13:10:55 Z flappybird Toll (BOI17_toll) C++17
7 / 100
 282 ms 259288 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 50505
#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++) if (i + (1 << j - 1) <= X + 1) 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:70: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   38 |  for (j = 1; j < MAXS; j++) for (i = 0; i <= X; i++) if (i + (1 << j - 1) <= X + 1) sp[i][j] = sp[i][j - 1] + sp[i + (1 << j - 1)][j - 1];
      |                                                                    ~~^~~
toll.cpp:38:126: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   38 |  for (j = 1; j < MAXS; j++) for (i = 0; i <= X; i++) if (i + (1 << j - 1) <= X + 1) 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 217 ms 75212 KB Output is correct
2 Correct 101 ms 74108 KB Output is correct
3 Correct 100 ms 74216 KB Output is correct
4 Correct 100 ms 74212 KB Output is correct
5 Correct 106 ms 74180 KB Output is correct
6 Correct 103 ms 74156 KB Output is correct
7 Correct 104 ms 74252 KB Output is correct
8 Correct 221 ms 75108 KB Output is correct
9 Correct 214 ms 75136 KB Output is correct
10 Correct 191 ms 74356 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 129628 KB Output is correct
2 Correct 102 ms 74184 KB Output is correct
3 Runtime error 231 ms 259288 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 102 ms 74232 KB Output is correct
2 Runtime error 227 ms 259276 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 102 ms 74232 KB Output is correct
2 Runtime error 227 ms 259276 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 217 ms 75212 KB Output is correct
2 Correct 101 ms 74108 KB Output is correct
3 Correct 100 ms 74216 KB Output is correct
4 Correct 100 ms 74212 KB Output is correct
5 Correct 106 ms 74180 KB Output is correct
6 Correct 103 ms 74156 KB Output is correct
7 Correct 104 ms 74252 KB Output is correct
8 Correct 221 ms 75108 KB Output is correct
9 Correct 214 ms 75136 KB Output is correct
10 Correct 191 ms 74356 KB Output is correct
11 Correct 282 ms 129628 KB Output is correct
12 Correct 102 ms 74184 KB Output is correct
13 Runtime error 231 ms 259288 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -