# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
951876 |
2024-03-22T21:29:59 Z |
inkvizytor |
Toll (BOI17_toll) |
C++11 |
|
252 ms |
98240 KB |
#include <bits/stdc++.h>
using namespace std;
int k, l;
int logarytm(int a) {
int w = 0;
while (a > 0) {
w++;
a /= 2;
}
return w+1;
}
vector<int> polacz(int a, vector<int> b) {
vector<int> w (k, -1);
if (a == -1) {
return w;
}
for (int i = 0; i < k; i++) {
if (b[i] != -1) {
w[i] = b[i]+a;
}
}
return w;
}
vector<int> mini(vector<int> a, vector<int> b) {
vector<int> w (k, 0);
for (int i = 0; i < k; i++) {
if (a[i]==-1 || b[i]==-1) {
w[i] = max(a[i], b[i]);
}
else {
w[i] = min(a[i], b[i]);
}
}
return w;
}
vector<vector<vector<int>>> jp;
vector<vector<vector<int>>> jp2;
vector<int> pot = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384};
int droga (int a, int b) {
int x = a/k, y = b/k, r = b%k;
int p = l-1;
vector<int> odl (5, -1);
odl[a%k] = 0;
while (p >= 0) {
if (x+pot[p]<=y) {
vector<int> pom (k, -1);
for (int i = 0; i < k; i++) {
pom = mini(pom, polacz(odl[i], jp[p][x*k+i]));
}
odl = pom;
x += pot[p];
}
p--;
}
return odl[r];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, o;
cin >> k >> n >> m >> o;
vector<vector<pair<int, int>>> g (n);
l = logarytm((n/k)+1);
jp.resize(l, vector<vector<int>>(n, vector<int>(k, -1)));
jp2.resize(l, vector<vector<int>>(n, vector<int>(k, -1)));
for (int i = 0; i < m; i++) {
int a, b, t;
cin >> a >> b >> t;
g[a].push_back(make_pair(b, t));
jp[0][a][b%k] = t;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
jp2[0][i][j] = (i/k)*k+k+j;
if (jp2[0][i][j] >= n) {
jp2[0][i][j] = n-1;
}
}
}
for (int i = 1; i < l; i++) {
for (int j = 0; j < n; j++) {
for (int x = 0; x < k; x++) {
jp2[i][j][x] = jp2[i-1][jp2[i-1][j][0]][x];
}
}
}
for (int i = 1; i < l; i++) {
for (int j = 0; j < n; j++) {
for (int x = 0; x < k; x++) {
jp[i][j] = mini(jp[i][j], polacz(jp[i-1][j][x], jp[i-1][jp2[i-1][j][x]]));
}
}
}
for (int i = 0; i < o; i++) {
int a, b;
cin >> a >> b;
cout << droga(a, b) << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
193 ms |
98240 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
252 ms |
93628 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
1628 KB |
Output is correct |
7 |
Correct |
3 ms |
1628 KB |
Output is correct |
8 |
Correct |
6 ms |
1628 KB |
Output is correct |
9 |
Correct |
5 ms |
1372 KB |
Output is correct |
10 |
Incorrect |
164 ms |
98144 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
1628 KB |
Output is correct |
7 |
Correct |
3 ms |
1628 KB |
Output is correct |
8 |
Correct |
6 ms |
1628 KB |
Output is correct |
9 |
Correct |
5 ms |
1372 KB |
Output is correct |
10 |
Incorrect |
164 ms |
98144 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
193 ms |
98240 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |