# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
869084 |
2023-11-03T06:29:24 Z |
quandlm |
Toll (BOI17_toll) |
C++14 |
|
98 ms |
191052 KB |
#include <bits/stdc++.h>
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, a, b) for (int i = (a); i >= (b); --i)
#define pi pair<int,int>
#define ple tuple<int,int,int>
#define fi first
#define se second
#define ii make_pair
#define isz(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define int long long
using namespace std;
const int N = 5e4 + 10;
const int lg = 17;
const int inf = 1e18;
int n, q, k, m, lim;
bool have[N][lg+2];
vector<int> adj[N];
int res[5][5], tmp[5][5], dp[N][lg+2][5][5];
void minimize (int &a, int b) {
a = min(a, b);
}
int bit (int i, int a) {
return (a >> i) & 1;
}
void Merge (int h[5][5], int g[5][5], int f[5][5]) {
for(int x = 0; x < k; ++x) {
for(int y = 0; y < k; ++y) {
for (int z = 0; z < k; ++z) {
minimize(h[x][z], g[x][y] + f[y][z]);
}
}
}
}
void reset(int x[5][5]) {
for(int i=0; i<k;++i) {
for(int j=0;j<k;++j) {
x[i][j]=inf;
}
}
}
void recur() {
for(int i=0;i<k;++i) {
for(int j=0;j<k;++j) {
res[i][j]=tmp[i][j];
}
}
}
int solve (int u, int v) {
int st = u / k;
int ed = v / k;
int cur = st;
for (int i = lg; i >= 0; --i) {
if (cur + (1 << i) <= ed) {
reset(tmp);
Merge(tmp, res, dp[cur][i]);
recur();
cur += (1 << i);
}
}
int ans = res[u%k][v%k];
if (ans == inf) ans=-1;
return ans;
}
main () {
file("toll");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> k >> n >> m >> q;
FOR(i,0,n) {
FOR(j,0,lg) {
FOR(x,0,k) {
FOR(y,0,k) {
dp[i][j][x][y] = inf;
}
}
}
}
FOR(i,1,m) {
int u,v,w; cin >> u >> v >> w;
dp[u/k][0][u%k][v%k] = w;
}
lim = n / k + 1;
for (int j = 1; j <= lg; ++j) {
for (int i = 0; i + (1 << j) - 1 <= lim; ++i) {
Merge(dp[i][j], dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
}
}
while(q--) {
int s, t; cin >> s >> t;
reset(res);
for (int i = 0; i < k; ++i) res[i][i] = 0;
cout << solve(s, t) << '\n';
}
}
/// code by yourlove
Compilation message
toll.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
77 | main () {
| ^~~~
toll.cpp: In function 'int main()':
toll.cpp:2:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
2 | #define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:78:5: note: in expansion of macro 'file'
78 | file("toll");
| ^~~~
toll.cpp:2:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
2 | #define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:78:5: note: in expansion of macro 'file'
78 | file("toll");
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
187612 KB |
Output is correct |
2 |
Correct |
1 ms |
2648 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
2 ms |
7004 KB |
Output is correct |
6 |
Correct |
2 ms |
7004 KB |
Output is correct |
7 |
Correct |
2 ms |
7256 KB |
Output is correct |
8 |
Correct |
47 ms |
188512 KB |
Output is correct |
9 |
Correct |
48 ms |
188292 KB |
Output is correct |
10 |
Correct |
35 ms |
187552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
187472 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
4 ms |
7000 KB |
Output is correct |
8 |
Correct |
5 ms |
7000 KB |
Output is correct |
9 |
Correct |
43 ms |
188312 KB |
Output is correct |
10 |
Correct |
75 ms |
189700 KB |
Output is correct |
11 |
Correct |
70 ms |
189264 KB |
Output is correct |
12 |
Correct |
61 ms |
188828 KB |
Output is correct |
13 |
Correct |
61 ms |
118100 KB |
Output is correct |
14 |
Correct |
42 ms |
117024 KB |
Output is correct |
15 |
Correct |
50 ms |
116816 KB |
Output is correct |
16 |
Correct |
50 ms |
116820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
7004 KB |
Output is correct |
7 |
Correct |
2 ms |
7000 KB |
Output is correct |
8 |
Correct |
2 ms |
7004 KB |
Output is correct |
9 |
Correct |
2 ms |
7004 KB |
Output is correct |
10 |
Correct |
40 ms |
188368 KB |
Output is correct |
11 |
Correct |
60 ms |
189008 KB |
Output is correct |
12 |
Correct |
74 ms |
189600 KB |
Output is correct |
13 |
Correct |
71 ms |
189844 KB |
Output is correct |
14 |
Correct |
60 ms |
189220 KB |
Output is correct |
15 |
Correct |
42 ms |
116752 KB |
Output is correct |
16 |
Correct |
45 ms |
116928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
7004 KB |
Output is correct |
7 |
Correct |
2 ms |
7000 KB |
Output is correct |
8 |
Correct |
2 ms |
7004 KB |
Output is correct |
9 |
Correct |
2 ms |
7004 KB |
Output is correct |
10 |
Correct |
40 ms |
188368 KB |
Output is correct |
11 |
Correct |
60 ms |
189008 KB |
Output is correct |
12 |
Correct |
74 ms |
189600 KB |
Output is correct |
13 |
Correct |
71 ms |
189844 KB |
Output is correct |
14 |
Correct |
60 ms |
189220 KB |
Output is correct |
15 |
Correct |
42 ms |
116752 KB |
Output is correct |
16 |
Correct |
45 ms |
116928 KB |
Output is correct |
17 |
Correct |
64 ms |
189012 KB |
Output is correct |
18 |
Correct |
1 ms |
2652 KB |
Output is correct |
19 |
Correct |
1 ms |
2652 KB |
Output is correct |
20 |
Correct |
1 ms |
2652 KB |
Output is correct |
21 |
Correct |
1 ms |
2652 KB |
Output is correct |
22 |
Correct |
1 ms |
2652 KB |
Output is correct |
23 |
Correct |
2 ms |
7004 KB |
Output is correct |
24 |
Correct |
3 ms |
7004 KB |
Output is correct |
25 |
Correct |
5 ms |
7004 KB |
Output is correct |
26 |
Correct |
3 ms |
7004 KB |
Output is correct |
27 |
Correct |
43 ms |
188184 KB |
Output is correct |
28 |
Correct |
72 ms |
189728 KB |
Output is correct |
29 |
Correct |
69 ms |
190032 KB |
Output is correct |
30 |
Correct |
64 ms |
189268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
187612 KB |
Output is correct |
2 |
Correct |
1 ms |
2648 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
2 ms |
7004 KB |
Output is correct |
6 |
Correct |
2 ms |
7004 KB |
Output is correct |
7 |
Correct |
2 ms |
7256 KB |
Output is correct |
8 |
Correct |
47 ms |
188512 KB |
Output is correct |
9 |
Correct |
48 ms |
188292 KB |
Output is correct |
10 |
Correct |
35 ms |
187552 KB |
Output is correct |
11 |
Correct |
76 ms |
187472 KB |
Output is correct |
12 |
Correct |
1 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
1 ms |
2652 KB |
Output is correct |
15 |
Correct |
1 ms |
2652 KB |
Output is correct |
16 |
Correct |
1 ms |
2652 KB |
Output is correct |
17 |
Correct |
4 ms |
7000 KB |
Output is correct |
18 |
Correct |
5 ms |
7000 KB |
Output is correct |
19 |
Correct |
43 ms |
188312 KB |
Output is correct |
20 |
Correct |
75 ms |
189700 KB |
Output is correct |
21 |
Correct |
70 ms |
189264 KB |
Output is correct |
22 |
Correct |
61 ms |
188828 KB |
Output is correct |
23 |
Correct |
61 ms |
118100 KB |
Output is correct |
24 |
Correct |
42 ms |
117024 KB |
Output is correct |
25 |
Correct |
50 ms |
116816 KB |
Output is correct |
26 |
Correct |
50 ms |
116820 KB |
Output is correct |
27 |
Correct |
1 ms |
2648 KB |
Output is correct |
28 |
Correct |
1 ms |
2652 KB |
Output is correct |
29 |
Correct |
1 ms |
2652 KB |
Output is correct |
30 |
Correct |
1 ms |
2652 KB |
Output is correct |
31 |
Correct |
1 ms |
2652 KB |
Output is correct |
32 |
Correct |
1 ms |
7004 KB |
Output is correct |
33 |
Correct |
2 ms |
7000 KB |
Output is correct |
34 |
Correct |
2 ms |
7004 KB |
Output is correct |
35 |
Correct |
2 ms |
7004 KB |
Output is correct |
36 |
Correct |
40 ms |
188368 KB |
Output is correct |
37 |
Correct |
60 ms |
189008 KB |
Output is correct |
38 |
Correct |
74 ms |
189600 KB |
Output is correct |
39 |
Correct |
71 ms |
189844 KB |
Output is correct |
40 |
Correct |
60 ms |
189220 KB |
Output is correct |
41 |
Correct |
42 ms |
116752 KB |
Output is correct |
42 |
Correct |
45 ms |
116928 KB |
Output is correct |
43 |
Correct |
64 ms |
189012 KB |
Output is correct |
44 |
Correct |
1 ms |
2652 KB |
Output is correct |
45 |
Correct |
1 ms |
2652 KB |
Output is correct |
46 |
Correct |
1 ms |
2652 KB |
Output is correct |
47 |
Correct |
1 ms |
2652 KB |
Output is correct |
48 |
Correct |
1 ms |
2652 KB |
Output is correct |
49 |
Correct |
2 ms |
7004 KB |
Output is correct |
50 |
Correct |
3 ms |
7004 KB |
Output is correct |
51 |
Correct |
5 ms |
7004 KB |
Output is correct |
52 |
Correct |
3 ms |
7004 KB |
Output is correct |
53 |
Correct |
43 ms |
188184 KB |
Output is correct |
54 |
Correct |
72 ms |
189728 KB |
Output is correct |
55 |
Correct |
69 ms |
190032 KB |
Output is correct |
56 |
Correct |
64 ms |
189268 KB |
Output is correct |
57 |
Correct |
98 ms |
191052 KB |
Output is correct |
58 |
Correct |
45 ms |
188484 KB |
Output is correct |
59 |
Correct |
80 ms |
189264 KB |
Output is correct |