oj.uz

Submission #867160

# Submission time Handle Problem Language Result Execution time Memory
867160 2023-10-27T19:15:16 Z bobbilyking Toll (BOI17_toll) C++17
10 / 100
 267 ms 13704 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-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) if (l[i] <= thru and thru <= r[i]) 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);
    }
    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 58 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 102 ms 9876 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 1 ms 3672 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 4188 KB Output is correct
8 Correct 5 ms 4200 KB Output is correct
9 Correct 42 ms 7872 KB Output is correct
10 Correct 203 ms 12660 KB Output is correct
11 Correct 108 ms 10076 KB Output is correct
12 Correct 57 ms 8976 KB Output is correct
13 Correct 267 ms 13704 KB Output is correct
14 Correct 117 ms 9600 KB Output is correct
15 Correct 148 ms 8572 KB Output is correct
16 Correct 147 ms 8364 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 58 ms 7872 KB Output isn't correct
2 Halted 0 ms 0 KB -