oj.uz

Submission #867157

# Submission time Handle Problem Language Result Execution time Memory
867157 2023-10-27T19:02:33 Z bobbilyking Toll (BOI17_toll) C++17
10 / 100
 190 ms 13752 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

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, 1e18); 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();
        // assert(h < dist.size());
        if (d != dist[h]) continue;
        for (auto [x, w]: adj[h]) if (l <= x and x <= r){
            x-=l;
            // assert(x < dist.size());
            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;
    if (lb == rb) {
        // All queries are just zero
        for (auto x: q) ans[x] = 0;
        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-k-1), min(rb, m+k+1)+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]);
    }

    // Remove all edges that "cross over"
    // F(i, lb, m) {
    //     {
    //         vector<pl> nadj;
    //         copy_if(A(adj[i]), back_inserter(nadj), [m](const auto &x) {return x.K < m;});
    //         swap(adj[i], nadj);
    //     }
    //     {
    //         vector<pl> nadj;
    //         copy_if(A(radj[i]), back_inserter(nadj), [m](const auto &x) {return x.K < m;});
    //         swap(adj[i], nadj);
    //     }
    // }
    // F(i, m+1, rb+1) {
    //     {
    //         vector<pl> nadj;
    //         copy_if(A(adj[i]), back_inserter(nadj), [m](const auto &x) {return x.K > m;});
    //         swap(adj[i], nadj);
    //     }
    //     {
    //         vector<pl> nadj;
    //         copy_if(A(adj[i]), back_inserter(nadj), [m](const auto &x) {return x.K > m;});
    //         swap(radj[i], nadj);
    //     }
    // }
    
    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);
    }
    ll inf = 1e18;
    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 47 ms 7872 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 84 ms 10156 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 2 ms 3804 KB Output is correct
5 Correct 2 ms 3652 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 3 ms 4188 KB Output is correct
8 Correct 4 ms 4188 KB Output is correct
9 Correct 32 ms 7872 KB Output is correct
10 Correct 144 ms 12648 KB Output is correct
11 Correct 98 ms 10064 KB Output is correct
12 Correct 43 ms 8928 KB Output is correct
13 Correct 190 ms 13752 KB Output is correct
14 Correct 84 ms 9600 KB Output is correct
15 Correct 95 ms 8324 KB Output is correct
16 Correct 94 ms 8328 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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