oj.uz

Submission #867164

# Submission time Handle Problem Language Result Execution time Memory
867164 2023-10-27T19:20:54 Z bobbilyking Toll (BOI17_toll) C++17
10 / 100
 1972 ms 14124 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

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

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)

#define NN 50010
#define M 1000000007 // 998244353

constexpr ll inf = 1e18;
vector<pl> adj[NN];
vector<pl> radj[NN];
ll ans[NN], l[NN], r[NN];
ll k;
ll n;

// returns array of size r-l+1, indexed with l 
vector<ll> dij(ll l, ll r, ll v, const vector<pl> (&adj)[NN]) {
    vector<ll> dist(r-l+1, inf); v-=l;
    dist[v] = 0;
    priority_queue<pl, vector<pl>, greater<pl>> pq;
    pq.emplace(dist[v], v);
    
    while (pq.size()) {
        auto [d, h] = pq.top(); pq.pop();
        if (d != dist[h]) continue;
        for (auto [x, w]: adj[h]) if (l <= x and x <= r){
            x-=l;
            if (d + w < dist[x]) {
                dist[x] = d + w;
                pq.emplace(dist[x], x);
            } 
        }
    }
    
    return dist;
}

void solve(ll lb, ll rb, vector<ll>& q) {
    if (lb >= rb) return;

    vector<ll> lq, rq;
    ll m = (lb+rb)/2;

    // All queries will pass through the roads m-k, m+k
    F(thru, max(lb, m-100), min(rb, m + 100)+1) {
        auto out = dij(lb, rb, thru, adj);
        auto in = dij(lb, rb, thru, radj); 
        for (auto i: q) ans[i] = min(ans[i], in[l[i]-lb] + out[r[i]-lb]);
    }
    
    for (auto i: q) {
        if (r[i] < m) lq.push_back(i);
        else if (m < l[i]) rq.push_back(i);
    }
    solve(lb, m-1, lq);
    solve(m+1, rb, rq);
}

int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    cin >> k >> n;
     G(m) G(o)
    vector<ll> q;
    while(m--){
        G(a) G(b) G(x) adj[a].emplace_back(b, x); radj[b].emplace_back(a, x);
    }
    F(i, 0, o) {
        cin >> l[i] >> r[i]; q.push_back(i);
        ans[i] =inf;
    }
    solve(0, n-1, q);
    F(i, 0, o) cout << (ans[i] == inf ? -1: ans[i]) << '\n';
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 678 ms 8172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 859 ms 10460 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 2 ms 3672 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 11 ms 4188 KB Output is correct
8 Correct 17 ms 4168 KB Output is correct
9 Correct 208 ms 7892 KB Output is correct
10 Correct 1972 ms 12784 KB Output is correct
11 Correct 1184 ms 10040 KB Output is correct
12 Correct 160 ms 8944 KB Output is correct
13 Correct 1847 ms 14124 KB Output is correct
14 Correct 1111 ms 9628 KB Output is correct
15 Correct 995 ms 8348 KB Output is correct
16 Correct 1020 ms 8396 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Incorrect 1 ms 3676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Incorrect 1 ms 3676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 678 ms 8172 KB Output isn't correct
2 Halted 0 ms 0 KB -