Submission #388368

#	Time	Username	Problem	Language	Result	Execution time	Memory
388368		Sara	Toll (BOI17_toll)	C++14	100 / 100	182 ms	55380 KiB

toll

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define F first
#define S second
#define pb push_back
#define lc (ind << 1)
#define rc (lc | 1)
#define md ((b + e) >> 1)

const ll N = 5e4 + 5;
const ll M = 5 + 3;
const ll LOG = 17;
const ll INF = 1e18 + 5;
const ll ziad = 1e9 + 5;
const ll MOD = 1e9 + 7;

int k, n, m, q;
ll dis[N][LOG][M];
ll dist[2][M];

inline void build(){
    int ghar = (n - 1) / k;
    for (int i = 1; i < LOG; i ++){
        for (int A = 0; A < n; A ++){
            int X = A / k;
            int Y = X + (1 << (i - 1));
            int Z = Y + (1 << (i - 1));
            if (ghar < Z) break; 
            for (int j = 0; j < k; j ++){
                int B = Y * k + j;
                if (n <= B) break;
                for (int l = 0; l < k; l ++){
                    int C = Z * k + l;
                    if (n <= C) break;
                    dis[A][i][l] = min(dis[A][i][l], dis[A][i - 1][j] + dis[B][i - 1][l]);    
                }
            }
        }
    }
    return;
}

inline ll get(int s, int e){
    if (e / k <= s / k) return -1;
    memset(dist, 63, sizeof dist);
    dist[0][s % k] = 0;
    ll state = s / k;
    ll dif = e / k - s / k;
    for (int i = LOG - 1; i >= 0; i --){
        if ((dif >> i) & 1){
            for (int a = 0; a < k; a ++){
                int A = state * k + a;
                if (n <= A) break;
                for (int b = 0; b < k; b ++){
                    int B = (state + (1 << i)) * k + b;
                    if (n <= B) break;
                    dist[1][b] = min(dist[1][b], dist[0][a] + dis[A][i][b]);
                }
            }
            for (int j = 0; j < k; j ++){
                dist[0][j] = dist[1][j];
                dist[1][j] = INF;
            }
            state += (1 << i);
        }
    }
    if (ziad < dist[0][e % k]) return -1;
    return dist[0][e % k];
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    memset(dis, 63, sizeof dis);
    cin >> k >> n >> m >> q;
    for (int i = 0; i < m; i ++){
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][0][v % k] = w;
    }
    build();
    while (q --){
        int s, e;
        cin >> s >> e;
        cout << get(s, e) << '\n';
    }
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44