Submission #667397

#	Time	Username	Problem	Language	Result	Execution time	Memory
667397		Znb_Jfrian	Toll (BOI17_toll)	C++14	0 / 100	134 ms	146476 KiB

toll

//______________"In The Name Of GOD"______________

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


typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;


const int lg        = 20;
const int mod       = 1e9 + 7;
const ll  inf       = 1e15 + 100;
const int maxn      = 1e6 + 100;
    

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


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

inline 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 = 2 * nd + 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, inf), fill(pd + s * k, pd + e * k, inf);
        dp[v] = 0;
        for (int j = v; j < k * e; j ++){
            for (auto p : adj[j]){ 
                int u = p.F, w = p.S;
                dp[u] = min(dp[u], dp[j] + w);
            }
        }
        pd[v] = 0;
        for (int j = v; j >= s * k; j --){
            for (auto p : jda[j]){
                int u = p.F, w = p.S;
                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;
}

inline 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, q;
    cin >> k >> n >> m >> q;
    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});
        jda[u].pb({v, t});
    }
    fill(ans, ans + q, inf);
    for (int i = 0; i < q; 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 < q; i ++) cout << (ans[i] >= mod ? -1 : ans[i]) << '\n';
    return 0;
}
/*test case :

*/

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