Submission #867152

#	Time	Username	Problem	Language	Result	Execution time	Memory
867152		bobbilyking	Toll (BOI17_toll)	C++17	0 / 100	66 ms	18156 KiB

toll

#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]) {
            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';
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from toll.cpp:5:
toll.cpp: In function 'std::vector<long long int> dij(ll, ll, ll, const std::vector<std::pair<long long int, long long int> > (&)[50010])':
toll.cpp:41:18: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<long long int, long long int> >::type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         assert(h < dist.size());
      |                ~~^~~~~~~~~~~~~
toll.cpp:45:22: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::pair<long long int, long long int> >::type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             assert(x < dist.size());
      |                    ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44