Submission #667231

#	Time	Username	Problem	Language	Result	Execution time	Memory
667231		Sogol	Toll (BOI17_toll)	C++17	0 / 100	122 ms	144988 KiB

toll

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
 
#define pb       push_back
#define Sz(x)    int((x).size())
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
 
const int maxn  =  1e6   + 10;
const int maxa  =  2e9   +  5;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;
const double eps = 1e-9;

int a[maxn], b[maxn], dp[maxn], pd[maxn], ans[maxn], n, k, bl;
vector <pair <int, int> > adj[maxn], ajd[maxn];
vector <int> qu[4 * maxn];

void avocado(int nd = 1, int s = 0, int e = bl){
    if (e - s == 1) return;
    int mid = (s + e) / 2, lc = 2 * nd, rc = lc + 1;
    avocado(lc, s, mid);
    avocado(rc, mid, e);
    for (int i = 0; i < k; i ++){
        int v = mid * k + i;
        if(v >= n) break;
        fill(dp + s * k, dp + e * k, mod);
        fill(pd + s * k, pd + e * k, mod);
        dp[v] = 0;
        for (int j = v; j < k * e; j ++){
            for (auto p : adj[j]){ 
                int u = p.fi, w = p.se;
                dp[u] = min(dp[u], dp[j] + w);
            }
        }
        pd[v] = 0;
        for (int j = v; j >= s * k; j --){
            for (auto p : ajd[j]){
                int u = p.fi, w = p.se;
                pd[u] = min(pd[u], pd[j] + w);
            }
        }
        for (int x : qu[nd]){
            ans[x] = min(ans[x], pd[a[x]] + dp[b[x]]);
        }
    }
    return;
}

int find(int l, int r, int v = 1, int s = 0, int e = bl){
    if(e - s == 1) return v;
    int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
    if(r < mid) return find(l, r, lc, s, mid);
    if(mid < l) return find(l, r, rc, mid, e);
    return v;
}

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int m, o;
    cin >> k >> n >> m >> o;
    bl = (n + k - 1) / k;
    for (int i = 0; i < m; i ++){
        int v, u, t;
        cin >> v >> u >> t;
        adj[v].pb({u, t});
        ajd[u].pb({v, t});
    }
    fill(ans, ans + o, mod);
    for (int i = 0; i < o; i ++){
        cin >> a[i] >> b[i];
        if(a[i] > b[i]) continue;
        qu[find(a[i] / k, b[i] / k + 1)].pb(i);
    }
    avocado();
    for (int i = 0; i < o; i ++) cout << (ans[i] >= mod ? -1 : ans[i]) << '\n';
    return 0;
}

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