oj.uz

Submission #674674

# Submission time Handle Problem Language Result Execution time Memory
674674 2022-12-25T18:47:37 Z AmirH Toll (BOI17_toll) C++14
46 / 100
 3000 ms 143356 KB 
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<bitset>
#include<queue>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<unordered_map>
#include<list>
#include<utility>
#include<stack>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
#define cl clear
#define F  first
#define S  second
#define pb push_back
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int MAX_N = 2e5 + 25;
const ll INF = 1e10;
const int inf = 1e9;
const int lgg = 17;
int k, n, m, q;
vector<pii> adj[MAX_N];
ll lift[MAX_N][lgg][5];
void free() {
    #ifndef ONLINE_JUDGE
        freopen("inputi.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
}

void build() {
    for(int i = 0; i < lgg; i++) {
        for(int j = 0; j < n; j++) {
            if(i == 0) {
                for(auto p : adj[j]) {
                    int x = p.first%k;
                    lift[j][i][x] = p.second;
                    //cout << i << " " << j << " " << x << " " << lift[j][i][x] << '\n';
                }
                continue;
            }
            for(int p = 0; p < k; p++) {
                for(int o = 0; o < k; o++) {
                    int x = j / k + (1 << (i - 1));
                    x = (x * k);
                    x+= o;
                    lift[j][i][p] = min(lift[j][i][p], lift[j][i-1][o] + lift[x][i - 1][p]);
                }
                //cout << i << " " << j << " " << p << " " << lift[j][i][p] << '\n';
            }
        }
    }
}

void setdef() {
    for(int i = 0; i < MAX_N; i++) {
        for(int j = 0; j < lgg; j++) {
            for(int p = 0; p < 5; p++)
                lift[i][j][p] = INF;
        }
    }
}

ll get_min(int x, int h, int p) {
    //cout << x << " " << h << " " << p << '\n';
    if(h == 0) {
        if(x%k == p)
            return 0;
        else
            return INF;
    }
    int chap = 31 - __builtin_clz(h);
    ll res = INF;
    for(int i = 0; i < k; i++) {
        int y = x / k + (1 << (chap));
        y = (y * k);
        y+= i;
        //cout << "!! " << lift[x][chap][i] << '\n';
        res = min(res, lift[x][chap][i] + get_min(y, h - (1 << chap), p));
    }
    return res;
}

void solve() {
    build();
    while(q--) {
        int x, y; cin >> x >> y;
        int hx = x / k;
        int hy = y / k;
        if(hy < hx) {
            cout << -1 << '\n';
        }
        else {
            ll res = get_min(x, hy - hx, y%k);
            if(res >= INF)
                cout << -1 << '\n';
            else
                cout << res << '\n';
        }
    }
}

void input() {
    cin >> k >> n >> m >> q;
    for(int i = 1; i <= m; i++) {
        int x, y, z; cin >> x >> y >> z;
        adj[x].pb({y, z});
    }
}
int main() {
    faster;// free();
    input();
    setdef();
    solve();
}

Compilation message

toll.cpp: In function 'void free()':
toll.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen("inputi.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 140568 KB Output is correct
2 Correct 54 ms 138020 KB Output is correct
3 Correct 53 ms 138064 KB Output is correct
4 Correct 54 ms 138024 KB Output is correct
5 Correct 57 ms 138144 KB Output is correct
6 Correct 55 ms 138060 KB Output is correct
7 Correct 55 ms 138152 KB Output is correct
8 Correct 86 ms 140560 KB Output is correct
9 Correct 85 ms 140492 KB Output is correct
10 Correct 69 ms 138188 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 141380 KB Output is correct
2 Correct 57 ms 138060 KB Output is correct
3 Correct 57 ms 138056 KB Output is correct
4 Correct 61 ms 138072 KB Output is correct
5 Correct 59 ms 137968 KB Output is correct
6 Correct 52 ms 138060 KB Output is correct
7 Correct 56 ms 138220 KB Output is correct
8 Correct 68 ms 138288 KB Output is correct
9 Correct 86 ms 140456 KB Output is correct
10 Correct 1834 ms 142956 KB Output is correct
11 Correct 158 ms 141384 KB Output is correct
12 Correct 1777 ms 140892 KB Output is correct
13 Execution timed out 3071 ms 143224 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 138032 KB Output is correct
2 Correct 57 ms 138092 KB Output is correct
3 Correct 53 ms 138008 KB Output is correct
4 Correct 54 ms 138084 KB Output is correct
5 Correct 54 ms 138100 KB Output is correct
6 Correct 56 ms 138124 KB Output is correct
7 Correct 57 ms 138036 KB Output is correct
8 Correct 64 ms 138220 KB Output is correct
9 Correct 59 ms 138156 KB Output is correct
10 Correct 86 ms 140408 KB Output is correct
11 Correct 111 ms 141168 KB Output is correct
12 Correct 161 ms 142712 KB Output is correct
13 Correct 189 ms 143356 KB Output is correct
14 Correct 151 ms 141964 KB Output is correct
15 Correct 325 ms 140584 KB Output is correct
16 Correct 744 ms 140580 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 138032 KB Output is correct
2 Correct 57 ms 138092 KB Output is correct
3 Correct 53 ms 138008 KB Output is correct
4 Correct 54 ms 138084 KB Output is correct
5 Correct 54 ms 138100 KB Output is correct
6 Correct 56 ms 138124 KB Output is correct
7 Correct 57 ms 138036 KB Output is correct
8 Correct 64 ms 138220 KB Output is correct
9 Correct 59 ms 138156 KB Output is correct
10 Correct 86 ms 140408 KB Output is correct
11 Correct 111 ms 141168 KB Output is correct
12 Correct 161 ms 142712 KB Output is correct
13 Correct 189 ms 143356 KB Output is correct
14 Correct 151 ms 141964 KB Output is correct
15 Correct 325 ms 140584 KB Output is correct
16 Correct 744 ms 140580 KB Output is correct
17 Correct 131 ms 141132 KB Output is correct
18 Correct 54 ms 138004 KB Output is correct
19 Correct 54 ms 138072 KB Output is correct
20 Correct 59 ms 138016 KB Output is correct
21 Correct 53 ms 138092 KB Output is correct
22 Correct 58 ms 138092 KB Output is correct
23 Correct 73 ms 138104 KB Output is correct
24 Correct 63 ms 138092 KB Output is correct
25 Correct 99 ms 138256 KB Output is correct
26 Correct 78 ms 138116 KB Output is correct
27 Correct 107 ms 140492 KB Output is correct
28 Correct 482 ms 142776 KB Output is correct
29 Correct 424 ms 143300 KB Output is correct
30 Correct 453 ms 142040 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 140568 KB Output is correct
2 Correct 54 ms 138020 KB Output is correct
3 Correct 53 ms 138064 KB Output is correct
4 Correct 54 ms 138024 KB Output is correct
5 Correct 57 ms 138144 KB Output is correct
6 Correct 55 ms 138060 KB Output is correct
7 Correct 55 ms 138152 KB Output is correct
8 Correct 86 ms 140560 KB Output is correct
9 Correct 85 ms 140492 KB Output is correct
10 Correct 69 ms 138188 KB Output is correct
11 Correct 160 ms 141380 KB Output is correct
12 Correct 57 ms 138060 KB Output is correct
13 Correct 57 ms 138056 KB Output is correct
14 Correct 61 ms 138072 KB Output is correct
15 Correct 59 ms 137968 KB Output is correct
16 Correct 52 ms 138060 KB Output is correct
17 Correct 56 ms 138220 KB Output is correct
18 Correct 68 ms 138288 KB Output is correct
19 Correct 86 ms 140456 KB Output is correct
20 Correct 1834 ms 142956 KB Output is correct
21 Correct 158 ms 141384 KB Output is correct
22 Correct 1777 ms 140892 KB Output is correct
23 Execution timed out 3071 ms 143224 KB Time limit exceeded
24 Halted 0 ms 0 KB -