oj.uz

Submission #715280

# Submission time Handle Problem Language Result Execution time Memory
715280 2023-03-26T11:06:44 Z ssense Toll (BOI17_toll) C++14
100 / 100
 477 ms 54736 KB 
#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
//#define int long long
#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu

const int N = 50000;

vector<pair<int, int>> bruh[20][N+5];

void solve()
{
    int n, m, o, k;
    cin >> k >> n >> m >> o;
    for(int i = 0; i < m; i++)
    {
        int u, v, t;
        cin >> u >> v >> t;
        bruh[0][u].push_back({v, t});
    }
    for(int i = 1; i <= 20; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(j/k+(1<<i) > (n-1)/k){break;}
            vector<pair<int, int>> now;
            for(auto p : bruh[i-1][j])
            {
                for(auto p2: bruh[i-1][p.fr])
                {
                    now.push_back({p2.fr, p.sc+p2.sc});
                }
            }
            sort(all(now));
            for(int br = 0; br < now.size(); br++)
            {
                if(br == 0 || now[br].fr != now[br-1].fr)
                {
                    bruh[i][j].push_back(now[br]);
                }
            }
        }
    }
    while(o--)
    {
        int a, b;
        cin >> a >> b;
        vector<pair<int, int>> now, now2;
        now.push_back({a, 0});
        while(true)
        {
            int dist = b/k-a/k;
            if(dist <= 0)
            {
                break;
            }
            int insp = 31-__builtin_clz(dist);
            for(auto p : now)
            {
                for(auto p2 : bruh[insp][p.fr])
                {
                    now2.push_back({p2.fr, p2.sc+p.sc});
                }
            }
            if(now2.empty()){break;}
            sort(all(now2));
            now.clear();
            for(int i = 0; i < now2.size(); i++)
            {
                if(i == 0 || now2[i].fr != now2[i-1].fr)
                {
                    now.push_back(now2[i]);
                }
            }
            now2.clear();
            a = now.front().fr;
        }
        if(now.empty()){
            cout << -1 << endl;
            continue;
        }
        bool flag = false;
        for(auto x : now)
        {
            if(x.fr == b)
            {
                cout << x.sc << endl;
                flag = true;
                break;
            }
        }
        if(!flag)
        {
            cout << -1 << endl;
        }
    }
}

int32_t main(){
    startt
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}


/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
 */

Compilation message

toll.cpp: In member function 'void prefix_sum::build(std::vector<int>)':
toll.cpp:20:667: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         ~~^~~~~~~~~~
toll.cpp: In function 'void solve()':
toll.cpp:50:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for(int br = 0; br < now.size(); br++)
      |                             ~~~^~~~~~~~~~~~
toll.cpp:83:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for(int i = 0; i < now2.size(); i++)
      |                            ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 46852 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 15 ms 23712 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 16 ms 23892 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 89 ms 38660 KB Output is correct
9 Correct 51 ms 30012 KB Output is correct
10 Correct 26 ms 23800 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 43552 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23716 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 14 ms 23988 KB Output is correct
8 Correct 22 ms 24056 KB Output is correct
9 Correct 70 ms 38648 KB Output is correct
10 Correct 290 ms 54372 KB Output is correct
11 Correct 175 ms 45188 KB Output is correct
12 Correct 98 ms 32112 KB Output is correct
13 Correct 398 ms 51484 KB Output is correct
14 Correct 161 ms 41384 KB Output is correct
15 Correct 287 ms 46952 KB Output is correct
16 Correct 270 ms 46800 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23736 KB Output is correct
3 Correct 13 ms 23768 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23852 KB Output is correct
7 Correct 17 ms 23996 KB Output is correct
8 Correct 20 ms 24336 KB Output is correct
9 Correct 18 ms 24080 KB Output is correct
10 Correct 73 ms 38868 KB Output is correct
11 Correct 195 ms 45048 KB Output is correct
12 Correct 326 ms 54192 KB Output is correct
13 Correct 321 ms 54616 KB Output is correct
14 Correct 255 ms 52744 KB Output is correct
15 Correct 291 ms 46816 KB Output is correct
16 Correct 274 ms 46800 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23736 KB Output is correct
3 Correct 13 ms 23768 KB Output is correct
4 Correct 15 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23852 KB Output is correct
7 Correct 17 ms 23996 KB Output is correct
8 Correct 20 ms 24336 KB Output is correct
9 Correct 18 ms 24080 KB Output is correct
10 Correct 73 ms 38868 KB Output is correct
11 Correct 195 ms 45048 KB Output is correct
12 Correct 326 ms 54192 KB Output is correct
13 Correct 321 ms 54616 KB Output is correct
14 Correct 255 ms 52744 KB Output is correct
15 Correct 291 ms 46816 KB Output is correct
16 Correct 274 ms 46800 KB Output is correct
17 Correct 200 ms 45140 KB Output is correct
18 Correct 13 ms 23796 KB Output is correct
19 Correct 12 ms 23804 KB Output is correct
20 Correct 13 ms 23684 KB Output is correct
21 Correct 11 ms 23764 KB Output is correct
22 Correct 11 ms 23692 KB Output is correct
23 Correct 16 ms 23892 KB Output is correct
24 Correct 17 ms 24056 KB Output is correct
25 Correct 28 ms 24276 KB Output is correct
26 Correct 26 ms 24140 KB Output is correct
27 Correct 88 ms 38640 KB Output is correct
28 Correct 312 ms 54256 KB Output is correct
29 Correct 328 ms 54736 KB Output is correct
30 Correct 277 ms 50616 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 46852 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 15 ms 23712 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 16 ms 23892 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 89 ms 38660 KB Output is correct
9 Correct 51 ms 30012 KB Output is correct
10 Correct 26 ms 23800 KB Output is correct
11 Correct 184 ms 43552 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 12 ms 23716 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Correct 14 ms 23988 KB Output is correct
18 Correct 22 ms 24056 KB Output is correct
19 Correct 70 ms 38648 KB Output is correct
20 Correct 290 ms 54372 KB Output is correct
21 Correct 175 ms 45188 KB Output is correct
22 Correct 98 ms 32112 KB Output is correct
23 Correct 398 ms 51484 KB Output is correct
24 Correct 161 ms 41384 KB Output is correct
25 Correct 287 ms 46952 KB Output is correct
26 Correct 270 ms 46800 KB Output is correct
27 Correct 12 ms 23764 KB Output is correct
28 Correct 13 ms 23736 KB Output is correct
29 Correct 13 ms 23768 KB Output is correct
30 Correct 15 ms 23764 KB Output is correct
31 Correct 13 ms 23764 KB Output is correct
32 Correct 13 ms 23852 KB Output is correct
33 Correct 17 ms 23996 KB Output is correct
34 Correct 20 ms 24336 KB Output is correct
35 Correct 18 ms 24080 KB Output is correct
36 Correct 73 ms 38868 KB Output is correct
37 Correct 195 ms 45048 KB Output is correct
38 Correct 326 ms 54192 KB Output is correct
39 Correct 321 ms 54616 KB Output is correct
40 Correct 255 ms 52744 KB Output is correct
41 Correct 291 ms 46816 KB Output is correct
42 Correct 274 ms 46800 KB Output is correct
43 Correct 200 ms 45140 KB Output is correct
44 Correct 13 ms 23796 KB Output is correct
45 Correct 12 ms 23804 KB Output is correct
46 Correct 13 ms 23684 KB Output is correct
47 Correct 11 ms 23764 KB Output is correct
48 Correct 11 ms 23692 KB Output is correct
49 Correct 16 ms 23892 KB Output is correct
50 Correct 17 ms 24056 KB Output is correct
51 Correct 28 ms 24276 KB Output is correct
52 Correct 26 ms 24140 KB Output is correct
53 Correct 88 ms 38640 KB Output is correct
54 Correct 312 ms 54256 KB Output is correct
55 Correct 328 ms 54736 KB Output is correct
56 Correct 277 ms 50616 KB Output is correct
57 Correct 477 ms 54360 KB Output is correct
58 Correct 82 ms 38604 KB Output is correct
59 Correct 214 ms 45308 KB Output is correct