oj.uz

Submission #916323

# Submission time Handle Problem Language Result Execution time Memory
916323 2024-01-25T16:25:55 Z trMatherz Toll (BOI17_toll) C++17
100 / 100
 802 ms 329908 KB 
#include <iostream> //cin, cout

/*
#include <fstream>
std::ifstream cin ("ex.in");
std::ofstream cout ("ex.out");
*/




// includes
#include <cmath> 
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>



//usings 
using namespace std;
using namespace __gnu_pbds;


// misc
#define ll long long
#define pb push_back
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; }
typedef uint64_t hash_t;

// vectors
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vppipi vector<pair<int, pair<int, int>>>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vpll vector<pair<ll, ll>>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define sz(x) (int)x.size()
#define rz resize
#define all(x) x.begin(), x.end()


// pairs
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define f first
#define s second

// sets
#define si set<int>
#define sl set<ll>
#define ss set<string>
#define in insert
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// maps
#define mii map<int, int>
#define mll map<ll, ll>

// loops
#define FR(x, z, y) for (int x = z; x < y; x++)
#define FRE(x, z, y) FR(x, z, y + 1)
#define F(x, y) FR(x, 0, y)
#define FE(x, y) F(x, y + 1)
#define A(x, y) for(auto &x : y)

vvl dp[50'005][17];

int main(){
    F(i, 50'005) F(j, 17) dp[i][j] = vvl(5, vl(5, 1e12));
    int k, n, m, q; cin >> k >> n >> m >> q;
    while(m--){
        int x, y, z; cin >> x >> y >> z;
        dp[x / k][0][x % k][y % k] = z;
    }
    FR(j, 1, 17) for(int i = 0; i + (1 << j) < (n + k - 1); i++) F(l, 5) F(p, 5) F(u, 5) 
        emin(dp[i][j][l][p], dp[i][j - 1][l][u] + dp[i + (1 << j - 1)][j - 1][u][p]);
    while(q--){
        int x, y; cin >> x >> y;
        vvl ans = vvl(5, vl(5, 1e12));
        F(i, 5) ans[i][i] = 0;
        int cur = x / k; int dest = y / k;
        for(int i = 16; i >= 0; i--){
                if(cur + (1 << i) > dest) continue;
                vvl temp = vvl(5, vl(5, 1e12));
                F(l, 5) F(p, 5) F(u, 5) 
                    emin(temp[l][p], ans[l][u] + dp[cur][i][u][p]);
                cur += (1 << i);
                ans = temp;
        } 
        cout << (ans[x % k][y % k] == 1e12 ? -1 : ans[x % k][y % k]) << endl;
    }
    
    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:100:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  100 |         emin(dp[i][j][l][p], dp[i][j - 1][l][u] + dp[i + (1 << j - 1)][j - 1][u][p]);
      |                                                                ~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 326468 KB Output is correct
2 Correct 292 ms 326432 KB Output is correct
3 Correct 317 ms 326408 KB Output is correct
4 Correct 287 ms 326228 KB Output is correct
5 Correct 310 ms 326228 KB Output is correct
6 Correct 297 ms 326284 KB Output is correct
7 Correct 299 ms 326480 KB Output is correct
8 Correct 697 ms 326488 KB Output is correct
9 Correct 708 ms 326496 KB Output is correct
10 Correct 662 ms 326424 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 326580 KB Output is correct
2 Correct 295 ms 326284 KB Output is correct
3 Correct 290 ms 326388 KB Output is correct
4 Correct 298 ms 326368 KB Output is correct
5 Correct 288 ms 326480 KB Output is correct
6 Correct 289 ms 326480 KB Output is correct
7 Correct 327 ms 326448 KB Output is correct
8 Correct 325 ms 326544 KB Output is correct
9 Correct 678 ms 327464 KB Output is correct
10 Correct 737 ms 328784 KB Output is correct
11 Correct 746 ms 328308 KB Output is correct
12 Correct 682 ms 327924 KB Output is correct
13 Correct 577 ms 328772 KB Output is correct
14 Correct 522 ms 327764 KB Output is correct
15 Correct 560 ms 327636 KB Output is correct
16 Correct 530 ms 327676 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 326224 KB Output is correct
2 Correct 289 ms 326296 KB Output is correct
3 Correct 288 ms 326264 KB Output is correct
4 Correct 299 ms 326416 KB Output is correct
5 Correct 287 ms 326288 KB Output is correct
6 Correct 289 ms 326288 KB Output is correct
7 Correct 298 ms 326512 KB Output is correct
8 Correct 297 ms 326484 KB Output is correct
9 Correct 296 ms 326680 KB Output is correct
10 Correct 630 ms 327208 KB Output is correct
11 Correct 653 ms 327912 KB Output is correct
12 Correct 679 ms 328528 KB Output is correct
13 Correct 708 ms 329044 KB Output is correct
14 Correct 676 ms 328244 KB Output is correct
15 Correct 505 ms 327680 KB Output is correct
16 Correct 513 ms 327652 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 326224 KB Output is correct
2 Correct 289 ms 326296 KB Output is correct
3 Correct 288 ms 326264 KB Output is correct
4 Correct 299 ms 326416 KB Output is correct
5 Correct 287 ms 326288 KB Output is correct
6 Correct 289 ms 326288 KB Output is correct
7 Correct 298 ms 326512 KB Output is correct
8 Correct 297 ms 326484 KB Output is correct
9 Correct 296 ms 326680 KB Output is correct
10 Correct 630 ms 327208 KB Output is correct
11 Correct 653 ms 327912 KB Output is correct
12 Correct 679 ms 328528 KB Output is correct
13 Correct 708 ms 329044 KB Output is correct
14 Correct 676 ms 328244 KB Output is correct
15 Correct 505 ms 327680 KB Output is correct
16 Correct 513 ms 327652 KB Output is correct
17 Correct 702 ms 328112 KB Output is correct
18 Correct 301 ms 326568 KB Output is correct
19 Correct 284 ms 326460 KB Output is correct
20 Correct 287 ms 326484 KB Output is correct
21 Correct 299 ms 326284 KB Output is correct
22 Correct 287 ms 326408 KB Output is correct
23 Correct 307 ms 326864 KB Output is correct
24 Correct 308 ms 326484 KB Output is correct
25 Correct 305 ms 326388 KB Output is correct
26 Correct 309 ms 326392 KB Output is correct
27 Correct 659 ms 327436 KB Output is correct
28 Correct 712 ms 328668 KB Output is correct
29 Correct 714 ms 329048 KB Output is correct
30 Correct 693 ms 328276 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 326468 KB Output is correct
2 Correct 292 ms 326432 KB Output is correct
3 Correct 317 ms 326408 KB Output is correct
4 Correct 287 ms 326228 KB Output is correct
5 Correct 310 ms 326228 KB Output is correct
6 Correct 297 ms 326284 KB Output is correct
7 Correct 299 ms 326480 KB Output is correct
8 Correct 697 ms 326488 KB Output is correct
9 Correct 708 ms 326496 KB Output is correct
10 Correct 662 ms 326424 KB Output is correct
11 Correct 757 ms 326580 KB Output is correct
12 Correct 295 ms 326284 KB Output is correct
13 Correct 290 ms 326388 KB Output is correct
14 Correct 298 ms 326368 KB Output is correct
15 Correct 288 ms 326480 KB Output is correct
16 Correct 289 ms 326480 KB Output is correct
17 Correct 327 ms 326448 KB Output is correct
18 Correct 325 ms 326544 KB Output is correct
19 Correct 678 ms 327464 KB Output is correct
20 Correct 737 ms 328784 KB Output is correct
21 Correct 746 ms 328308 KB Output is correct
22 Correct 682 ms 327924 KB Output is correct
23 Correct 577 ms 328772 KB Output is correct
24 Correct 522 ms 327764 KB Output is correct
25 Correct 560 ms 327636 KB Output is correct
26 Correct 530 ms 327676 KB Output is correct
27 Correct 330 ms 326224 KB Output is correct
28 Correct 289 ms 326296 KB Output is correct
29 Correct 288 ms 326264 KB Output is correct
30 Correct 299 ms 326416 KB Output is correct
31 Correct 287 ms 326288 KB Output is correct
32 Correct 289 ms 326288 KB Output is correct
33 Correct 298 ms 326512 KB Output is correct
34 Correct 297 ms 326484 KB Output is correct
35 Correct 296 ms 326680 KB Output is correct
36 Correct 630 ms 327208 KB Output is correct
37 Correct 653 ms 327912 KB Output is correct
38 Correct 679 ms 328528 KB Output is correct
39 Correct 708 ms 329044 KB Output is correct
40 Correct 676 ms 328244 KB Output is correct
41 Correct 505 ms 327680 KB Output is correct
42 Correct 513 ms 327652 KB Output is correct
43 Correct 702 ms 328112 KB Output is correct
44 Correct 301 ms 326568 KB Output is correct
45 Correct 284 ms 326460 KB Output is correct
46 Correct 287 ms 326484 KB Output is correct
47 Correct 299 ms 326284 KB Output is correct
48 Correct 287 ms 326408 KB Output is correct
49 Correct 307 ms 326864 KB Output is correct
50 Correct 308 ms 326484 KB Output is correct
51 Correct 305 ms 326388 KB Output is correct
52 Correct 309 ms 326392 KB Output is correct
53 Correct 659 ms 327436 KB Output is correct
54 Correct 712 ms 328668 KB Output is correct
55 Correct 714 ms 329048 KB Output is correct
56 Correct 693 ms 328276 KB Output is correct
57 Correct 802 ms 329908 KB Output is correct
58 Correct 681 ms 327312 KB Output is correct
59 Correct 721 ms 328140 KB Output is correct