oj.uz

Submission #674676

# Submission time Handle Problem Language Result Execution time Memory
674676 2022-12-25T18:55:03 Z AmirH Toll (BOI17_toll) C++14
0 / 100
 85 ms 73912 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 = 5e4 + 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;
                }
                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]);
                }
            }
        }
    }
}

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) {
    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;
        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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 73912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 73828 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34644 KB Output is correct
2 Runtime error 43 ms 70200 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34644 KB Output is correct
2 Runtime error 43 ms 70200 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 73912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -