oj.uz

Submission #480713

# Submission time Handle Problem Language Result Execution time Memory
480713 2021-10-17T23:22:03 Z hidden1 Toll (BOI17_toll) C++14
46 / 100
 3000 ms 16100 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e15 + 7;
#ifndef LOCAL
#define cerr if(false) cerr
#endif

typedef vector<vector<ll> > mat;

const ll MAX_N = 1e5 + 10;
ll n, m, k, q;

mat mult(const mat &a, const mat &b) {
    mat ret = mat(k, vector<ll>(k, mod));
    if(a.empty()) { return b; }
    if(b.empty()) { return a; }
    for(ll i = 0; i < k; i ++) {
        for(ll j = 0; j < k; j ++) {
            for(ll mid = 0; mid < k; mid ++) {
                chkmin(ret[i][j], a[i][mid] + b[mid][j]);
            }
        }
    }
    return ret;
}

mat prec[MAX_N], jmp[MAX_N];
const ll JMP = 750;
ll loc[MAX_N];

vector<pair<ll, ll> > g[MAX_N];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> k >> n >> m >> q;
    for(ll i = 0; i < m; i ++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    for(ll i = 0; i < n; i += k) {
        prec[i / k] = mat(k, vector<ll>(k, mod));
        for(ll j = i; j < i + k; j ++) {
            for(auto it : g[j]) {
                chkmin(prec[i / k][j % k][it.first % k], it.second);
            }
        }
    }
    fill(loc, loc + MAX_N, mod);
    for(ll i = (n + k - 1) / k; i >= 0; i --) {
        if(i % JMP == 0) {
            jmp[i / k] = prec[i / k];
            loc[i / k] = i / k + 1;
        } else {
            jmp[i / k] = mult(prec[i / k], jmp[i / k + 1]); 
            loc[i / k] = loc[i / k + 1];
        }
    }
    while(q --) {
        ll a, b;
        cin >> a >> b;
        if(a / k >= b / k) {
            cout << -1 << endl; 
            continue;
        } 
        mat ret = prec[a / k];
        a += k;

        ll gra = a / k, grb = b / k;

        while(gra < grb) {
            if(loc[gra] < grb) {
                ret = mult(ret, jmp[gra]);
                gra = loc[gra];
            } else {
                ret = mult(ret, prec[gra]);
                gra ++;
            }
        }
        if(ret[a % k][b % k] == mod) {
            cout << -1 << endl; 
        } else {
            cout << ret[a % k][b % k] << endl;
        }
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 15956 KB Output is correct
2 Correct 4 ms 8012 KB Output is correct
3 Correct 5 ms 8012 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 20 ms 8304 KB Output is correct
6 Correct 20 ms 8304 KB Output is correct
7 Correct 19 ms 8300 KB Output is correct
8 Correct 329 ms 16100 KB Output is correct
9 Correct 332 ms 15840 KB Output is correct
10 Correct 286 ms 14412 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 4 ms 8140 KB Output is correct
6 Correct 6 ms 8296 KB Output is correct
7 Correct 8 ms 8268 KB Output is correct
8 Correct 11 ms 8372 KB Output is correct
9 Correct 9 ms 8208 KB Output is correct
10 Correct 47 ms 15900 KB Output is correct
11 Correct 115 ms 15144 KB Output is correct
12 Correct 154 ms 15556 KB Output is correct
13 Correct 157 ms 15980 KB Output is correct
14 Correct 163 ms 14896 KB Output is correct
15 Correct 192 ms 12636 KB Output is correct
16 Correct 161 ms 12636 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 4 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 4 ms 8140 KB Output is correct
6 Correct 6 ms 8296 KB Output is correct
7 Correct 8 ms 8268 KB Output is correct
8 Correct 11 ms 8372 KB Output is correct
9 Correct 9 ms 8208 KB Output is correct
10 Correct 47 ms 15900 KB Output is correct
11 Correct 115 ms 15144 KB Output is correct
12 Correct 154 ms 15556 KB Output is correct
13 Correct 157 ms 15980 KB Output is correct
14 Correct 163 ms 14896 KB Output is correct
15 Correct 192 ms 12636 KB Output is correct
16 Correct 161 ms 12636 KB Output is correct
17 Correct 1658 ms 15300 KB Output is correct
18 Correct 6 ms 8012 KB Output is correct
19 Correct 5 ms 8140 KB Output is correct
20 Correct 5 ms 8140 KB Output is correct
21 Correct 5 ms 8140 KB Output is correct
22 Correct 4 ms 8140 KB Output is correct
23 Correct 47 ms 8268 KB Output is correct
24 Correct 72 ms 8268 KB Output is correct
25 Correct 129 ms 8332 KB Output is correct
26 Correct 111 ms 8432 KB Output is correct
27 Correct 121 ms 15872 KB Output is correct
28 Correct 2705 ms 15580 KB Output is correct
29 Correct 2661 ms 16076 KB Output is correct
30 Correct 2529 ms 14868 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 15956 KB Output is correct
2 Correct 4 ms 8012 KB Output is correct
3 Correct 5 ms 8012 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 20 ms 8304 KB Output is correct
6 Correct 20 ms 8304 KB Output is correct
7 Correct 19 ms 8300 KB Output is correct
8 Correct 329 ms 16100 KB Output is correct
9 Correct 332 ms 15840 KB Output is correct
10 Correct 286 ms 14412 KB Output is correct
11 Execution timed out 3066 ms 15328 KB Time limit exceeded
12 Halted 0 ms 0 KB -