Submission #674674

#	Time	Username	Problem	Language	Result	Execution time	Memory
674674		AmirH	Toll (BOI17_toll)	C++14	46 / 100	3071 ms	143356 KiB

toll

#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 (stderr)

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 / 7
• Subtask 2: 0 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 0 / 44