oj.uz

Submission #696958

# Submission time Handle Problem Language Result Execution time Memory
696958 2023-02-07T17:20:24 Z SOCIOPATE Toll (BOI17_toll) C++17
39 / 100
 3000 ms 12168 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3027 ms 6336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 8232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 29 ms 6568 KB Output is correct
11 Correct 93 ms 8396 KB Output is correct
12 Correct 127 ms 11248 KB Output is correct
13 Correct 149 ms 12144 KB Output is correct
14 Correct 114 ms 9672 KB Output is correct
15 Correct 61 ms 6348 KB Output is correct
16 Correct 54 ms 6356 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 29 ms 6568 KB Output is correct
11 Correct 93 ms 8396 KB Output is correct
12 Correct 127 ms 11248 KB Output is correct
13 Correct 149 ms 12144 KB Output is correct
14 Correct 114 ms 9672 KB Output is correct
15 Correct 61 ms 6348 KB Output is correct
16 Correct 54 ms 6356 KB Output is correct
17 Correct 1313 ms 8604 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 6 ms 464 KB Output is correct
24 Correct 13 ms 468 KB Output is correct
25 Correct 18 ms 696 KB Output is correct
26 Correct 16 ms 600 KB Output is correct
27 Correct 320 ms 6592 KB Output is correct
28 Correct 1957 ms 11272 KB Output is correct
29 Correct 2126 ms 12168 KB Output is correct
30 Correct 1445 ms 9920 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3027 ms 6336 KB Time limit exceeded
2 Halted 0 ms 0 KB -