oj.uz

Submission #536494

# Submission time Handle Problem Language Result Execution time Memory
536494 2022-03-13T12:32:31 Z KiriLL1ca Toll (BOI17_toll) C++14
0 / 100
 3000 ms 24604 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define endl '\n'
#define pb push_back
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)

#pragma GCC optimize ("-O3")
#pragma GCC optimize ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long double ld;

template <typename T> inline bool umax (T &a, const T &b) { return (a < b ? a = b, 1 : 0); }
template <typename T> inline bool umin (T &a, const T &b) { return (a > b ? a = b, 1 : 0); }

template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 5e4 + 100;
const int K = 5;

int block[N], ans[N];
vector <int> rblock[N];
vector <pii> g[N], rg[N];

inline void rec (int l, int r, vector <tuple <int, int, int>> query) {
    if (l >= r) return;
    int mid = (l + r) >> 1;

    vector <vector <int>> dist (K, vector <int> (N, 1e9));
    const int norm = rblock[mid][0];

    for (auto st : rblock[mid]) {
        priority_queue <pii, vector <pii>, greater <pii>> pq;
        pq.push({0, st}); dist[st - norm][st] = 0;

        while (!pq.empty()) {
            auto [d, v] = pq.top(); pq.pop();
            if (d > dist[st - norm][v]) continue;
            for (auto [u, w] : rg[v]) {
                if (dist[st - norm][u] > dist[st - norm][v] + w) {
                    dist[st - norm][u] = dist[st - norm][v] + w;
                    pq.push({dist[st - norm][u], u});
                }
            }
        }

        pq.push({0, st});
        while (!pq.empty()) {
            auto [d, v] = pq.top(); pq.pop();
            if (d > dist[st - norm][v]) continue;
            for (auto [u, w] : g[v]) {
                if (dist[st - norm][u] > dist[st - norm][v] + w) {
                    dist[st - norm][u] = dist[st - norm][v] + w;
                    pq.push({dist[st - norm][u], u});
                }
            }
        }
    }

    vector <tuple <int, int, int>> left, right;
    for (auto [l, r, idx] : query) {
        if (block[r] < mid) left.pb({l, r, idx});
        else if (block[l] > mid) right.pb({l, r, idx});
        else {
            for (auto j : rblock[mid]) {
                umin(ans[idx], dist[j - norm][l] + dist[j - norm][r]);
            }
        }
    }

    rec(l, mid - 1, left);
    rec(mid + 1, r, right);
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int k, n, m, q; cin >> k >> n >> m >> q;
    for (int i = 0; i < n; i++) {
        block[i] = i / k;
        rblock[i / k].pb(i);
    }
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        g[a].pb({b, c});
        rg[b].pb({a, c});
    }
    vector <tuple <int, int, int>> query (q);
    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;
        query[i] = {a, b, i};
    }
    fill(ans, ans + q, 1e9);
    rec(0, block[n - 1], query);
    for (int i = 0; i < q; i++) cout << (ans[i] == 1e9 ? -1 : ans[i]) << endl;
    return 0;
}

Compilation message

toll.cpp: In function 'void rec(int, int, std::vector<std::tuple<int, int, int> >)':
toll.cpp:49:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |             auto [d, v] = pq.top(); pq.pop();
      |                  ^
toll.cpp:51:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |             for (auto [u, w] : rg[v]) {
      |                       ^
toll.cpp:61:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |             auto [d, v] = pq.top(); pq.pop();
      |                  ^
toll.cpp:63:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |             for (auto [u, w] : g[v]) {
      |                       ^
toll.cpp:73:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for (auto [l, r, idx] : query) {
      |               ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 24604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 22716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7204 KB Output is correct
2 Correct 3 ms 6204 KB Output is correct
3 Correct 4 ms 6032 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 168 ms 13280 KB Output is correct
7 Correct 101 ms 12228 KB Output is correct
8 Correct 125 ms 11196 KB Output is correct
9 Correct 102 ms 11208 KB Output is correct
10 Execution timed out 3075 ms 24112 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7204 KB Output is correct
2 Correct 3 ms 6204 KB Output is correct
3 Correct 4 ms 6032 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 168 ms 13280 KB Output is correct
7 Correct 101 ms 12228 KB Output is correct
8 Correct 125 ms 11196 KB Output is correct
9 Correct 102 ms 11208 KB Output is correct
10 Execution timed out 3075 ms 24112 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 24604 KB Time limit exceeded
2 Halted 0 ms 0 KB -