oj.uz

Submission #867158

# Submission time Handle Problem Language Result Execution time Memory
867158 2023-10-27T19:05:25 Z bobbilyking Toll (BOI17_toll) C++17
10 / 100
 257 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();
        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;
    if (lb == rb) {
        // All queries are just zero
        for (auto x: q) {
            assert(l[x] == r[x]);
            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-2*k-1), min(rb, m+2*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 51 ms 7868 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 127 ms 9884 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 1 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 4184 KB Output is correct
8 Correct 5 ms 4188 KB Output is correct
9 Correct 33 ms 7872 KB Output is correct
10 Correct 196 ms 12688 KB Output is correct
11 Correct 119 ms 10064 KB Output is correct
12 Correct 54 ms 9020 KB Output is correct
13 Correct 257 ms 13752 KB Output is correct
14 Correct 116 ms 9604 KB Output is correct
15 Correct 154 ms 8328 KB Output is correct
16 Correct 146 ms 8356 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Incorrect 2 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 3672 KB Output is correct
2 Incorrect 2 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 51 ms 7868 KB Output isn't correct
2 Halted 0 ms 0 KB -