oj.uz

Submission #1097893

# Submission time Handle Problem Language Result Execution time Memory
1097893 2024-10-08T14:38:38 Z anhthi Toll (BOI17_toll) C++14
7 / 100
 203 ms 266324 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define heap priority_queue
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)

 
template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }
 
template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }
 
template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a));
        a.resize(unique(all(a)) - a.begin());
    }
 
int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) {
    return l + abs((ll) rng()) % (r - l + 1);
}
 
const ll oo = (ll) 1e17;
const int inf = (ll) 1e9 + 7, mod = (ll) 1e9 + 7;
 
const int N = 5e4 + 5, LOG = 16;
 
void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }

int k, n, m, q;

using matrix = vector<vector<ll>>;
#define intial(x) matrix(k, vector<ll>(k, x))

matrix f[N][LOG + 5];
matrix combine(matrix &x, matrix &y) {
    matrix res = intial(oo);
    forn(u, 0, k - 1) forn(v, 0, k - 1) forn(mid, 0, k - 1) {
        minimize(res[u][v], x[u][mid] + y[mid][v]);
    }
    return res;
}

int main(void) {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> k >> n >> m >> q;

    forn(i, 0, n * k) fill(f[i], f[i] + 1 + LOG, intial(oo));

    rep(i, m) {
        int u, v, w;
        cin >> u >> v >> w;
        f[u / k][0][u % k][v % k] = w;
    }

    rep(j, LOG) {
        forn(i, 0, (n - 1) / k - MASK(j)) {
            combine(f[i][j-1], f[i + MASK(j-1)][j-1]).swap(f[i][j]);
        }
    }

    rep(_, q) {
        int a, b;
        cin >> a >> b;

        if (a / k + 1 > b / k) {
            cout << -1 << '\n';
            continue;
        }

        matrix res = intial(0);

        int p = a / k;
        ford(i, LOG, 0) {
            if (p + MASK(i) <= b / k) {
                combine(res, f[p][i]).swap(res);
                p += MASK(i);
            }
        }

        ll ans = res[a % k][b % k];
        if (ans >= oo) cout << -1 << '\n';
        else cout << ans << '\n';

    }

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 79184 KB Output is correct
2 Correct 12 ms 24920 KB Output is correct
3 Correct 13 ms 24924 KB Output is correct
4 Correct 15 ms 24924 KB Output is correct
5 Correct 15 ms 26200 KB Output is correct
6 Correct 16 ms 26204 KB Output is correct
7 Correct 13 ms 26204 KB Output is correct
8 Correct 170 ms 79188 KB Output is correct
9 Correct 175 ms 79188 KB Output is correct
10 Correct 152 ms 78416 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 266324 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24920 KB Output is correct
2 Incorrect 10 ms 24940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24920 KB Output is correct
2 Incorrect 10 ms 24940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 79184 KB Output is correct
2 Correct 12 ms 24920 KB Output is correct
3 Correct 13 ms 24924 KB Output is correct
4 Correct 15 ms 24924 KB Output is correct
5 Correct 15 ms 26200 KB Output is correct
6 Correct 16 ms 26204 KB Output is correct
7 Correct 13 ms 26204 KB Output is correct
8 Correct 170 ms 79188 KB Output is correct
9 Correct 175 ms 79188 KB Output is correct
10 Correct 152 ms 78416 KB Output is correct
11 Runtime error 203 ms 266324 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -