oj.uz

Submission #867154

# Submission time Handle Problem Language Result Execution time Memory
867154 2023-10-27T18:59:17 Z bobbilyking Toll (BOI17_toll) C++17
10 / 100
 205 ms 15568 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;

    // construct radj on the fly
    F(i, lb, rb+1) radj[i].clear();
    F(i, lb, rb+1) for (auto [x, w]: adj[i]) if (lb <= x and x <= rb) radj[x].emplace_back(i, w);

    // 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);
    }
    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);
    }
    
    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); 
    }
    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 75 ms 7864 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 115 ms 9372 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 1 ms 3672 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 4 ms 4164 KB Output is correct
8 Correct 5 ms 4188 KB Output is correct
9 Correct 51 ms 8756 KB Output is correct
10 Correct 184 ms 14008 KB Output is correct
11 Correct 132 ms 11344 KB Output is correct
12 Correct 78 ms 9924 KB Output is correct
13 Correct 205 ms 15568 KB Output is correct
14 Correct 110 ms 10712 KB Output is correct
15 Correct 120 ms 9176 KB Output is correct
16 Correct 117 ms 9188 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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