oj.uz

Submission #867161

# Submission time Handle Problem Language Result Execution time Memory
867161 2023-10-27T19:17:03 Z bobbilyking Toll (BOI17_toll) C++14
10 / 100
 275 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;

    for (auto i: q) assert (lb <= l[i] and r[i] <= rb);

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

Compilation message

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:40:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |         auto [d, h] = pq.top(); pq.pop();
      |              ^
toll.cpp:42:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         for (auto [x, w]: adj[h]) if (l <= x and x <= r){
      |                   ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 7856 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 94 ms 9876 KB Output is correct
2 Correct 2 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 4044 KB Output is correct
8 Correct 5 ms 4188 KB Output is correct
9 Correct 40 ms 7872 KB Output is correct
10 Correct 197 ms 12660 KB Output is correct
11 Correct 108 ms 10068 KB Output is correct
12 Correct 49 ms 8964 KB Output is correct
13 Correct 275 ms 13704 KB Output is correct
14 Correct 123 ms 9596 KB Output is correct
15 Correct 145 ms 8356 KB Output is correct
16 Correct 145 ms 8328 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 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 2 ms 3676 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 7856 KB Output isn't correct
2 Halted 0 ms 0 KB -