Submission #696958

#	Time	Username	Problem	Language	Result	Execution time	Memory
696958		SOCIOPATE	Toll (BOI17_toll)	C++17	39 / 100	3063 ms	12168 KiB

toll

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define pll pair<ll, ll>
#define pii pair<int, int>
#define pdd pair<ld, ld>
#define ff first
#define ss second
#define all(v) v.begin(),v.end()

typedef tree<
    pii,
    null_type,
    less<pii>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordset;

#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")

ll INF = 2e18;
const ll mod = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll binpow(ll n, ll m){
    if(m == 0) return 1ll;
    if(m & 1ll) return (n * binpow(n, m - 1ll)) % mod;
    ll b = binpow(n, m / 2ll);
    return (b*b) % mod;
}

int n, k, m, o;
vector<vector<pll>> b, a;

ll ans[50005][19][22];

void dq(int l, int r, int lev){
    if(l > r) return;
    int m = (l + r) / 2;
    for(int i = m; i >= l; i--)
        for(int j = 0; j <= 4 * k; j++) ans[i][lev][j] = (i == m - j ? 0ll : INF);
    for(int i = m + 1; i <= r; i++){
        for(int j = 0; j <= 4* k; j++) ans[i][lev][j] = INF;
        for(pll u : b[i])
            for(int j = 0; j <= 4 * k; j++) ans[i][lev][j] = min(ans[i][lev][j], ans[u.ff][lev][j] + u.ss);
    }
    //cout << l << ' ' << r << ' ' << m << ' ' << lev << '\n';
    for(int i = m; i >= l; i--){
        for(pll u : a[i]){
            if(u.ff > m) continue;
            //cout << i << ' ' << u.ff << ' ' << u.ss << '\n';
            for(int j = 0; j <= 4* k; j++) ans[i][lev][j] = min(ans[i][lev][j], ans[u.ff][lev][j] + u.ss);
        }
    }
//    for(int i = l; i <= r; i++){
//        cout << i << '\n';
//        for(int j = 0; j <= 3 * k; j++) cout << ans[i][lev][j] << ' ';
//        cout << '\n';
//    }
    dq(l, m - 1, lev + 1);
    dq(m + 1, r, lev + 1);
}

ll ask(int l, int r, int lev, int a, int b){
    assert(l <= r);
    int m = (l + r) / 2;
    //cout << l << ' ' << r << ' ' << m << '\n';
    if(a <= m && m + 1 <= b){
        //cout << l << ' ' << r << ' ' << m << ' ' << a << ' ' << b << '\n';
        ll res = INF;
        for(int j = 0; j <= 4*k; j++) res = min(res, ans[a][lev][j] + ans[b][lev][j]);
        return res;
    }
    if(a < m && b == m) return ans[a][lev][0];
    if(a > m) return ask(m + 1, r, lev + 1, a, b);
    return ask(l, m - 1, lev + 1, a, b);
}

void solve(){
    cin >> k >> n >> m >> o;
    a.resize(n);
    b.resize(n);
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({v, w});
        b[v].push_back({u, w});
    }
    dq(0, n - 1, 0);
    for(int i = 0; i < o; i++){
        int u, v;
        cin >> u >> v;
        if(u == v){
            cout << 0 << '\n';
            continue;
        }
        if(u > v){
            cout << -1 << '\n';
            continue;
        }
        //cout << u << ' ' << v << '\n';
        ll res = ask(0, n - 1, 0, u, v);
        cout << (res == INF ? -1 : res) << '\n';
    }
}

void brute(){
    cin >> k >> n >> m >> o;
    a.resize(n);
    b.resize(n);
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        a[u].push_back({v, w});
        b[v].push_back({u, w});
    }
    vector<ll> dp(n);
    for(int i = 0; i < o; i++){
        int u, v;
        cin >> u >> v;
        dp.assign(n, INF);
        dp[u] = 0;
        for(; u < v; u++)
            for(pll p : a[u])
                dp[p.ff] = min(dp[p.ff], dp[u] + p.ss);
        cout << (dp[v] == INF ? -1 : dp[v]) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif
	int tt;
    //cin >> tt;
    tt = 1;
    while(tt--){
        //solve();
        brute();
		#ifdef LOCAL
            cout << "__________________________________" << endl;
		#endif
	}
	#ifdef LOCAL
        cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << "sec" << '\n';
	#endif
	return 0;
}

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