oj.uz

Submission #480712

# Submission time Handle Problem Language Result Execution time Memory
480712 2021-10-17T23:21:20 Z hidden1 Toll (BOI17_toll) C++14
46 / 100
 3000 ms 16068 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 = 300;
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 190 ms 15940 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 4 ms 8012 KB Output is correct
5 Correct 14 ms 8268 KB Output is correct
6 Correct 14 ms 8268 KB Output is correct
7 Correct 14 ms 8308 KB Output is correct
8 Correct 185 ms 15932 KB Output is correct
9 Correct 183 ms 15872 KB Output is correct
10 Correct 170 ms 14540 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8012 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 4 ms 8140 KB Output is correct
6 Correct 6 ms 8268 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 8268 KB Output is correct
10 Correct 41 ms 15880 KB Output is correct
11 Correct 116 ms 15172 KB Output is correct
12 Correct 147 ms 15552 KB Output is correct
13 Correct 159 ms 16012 KB Output is correct
14 Correct 183 ms 14836 KB Output is correct
15 Correct 189 ms 12700 KB Output is correct
16 Correct 160 ms 12608 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8012 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 4 ms 8140 KB Output is correct
6 Correct 6 ms 8268 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 8268 KB Output is correct
10 Correct 41 ms 15880 KB Output is correct
11 Correct 116 ms 15172 KB Output is correct
12 Correct 147 ms 15552 KB Output is correct
13 Correct 159 ms 16012 KB Output is correct
14 Correct 183 ms 14836 KB Output is correct
15 Correct 189 ms 12700 KB Output is correct
16 Correct 160 ms 12608 KB Output is correct
17 Correct 1588 ms 15196 KB Output is correct
18 Correct 5 ms 8140 KB Output is correct
19 Correct 4 ms 8140 KB Output is correct
20 Correct 4 ms 8140 KB Output is correct
21 Correct 5 ms 8140 KB Output is correct
22 Correct 5 ms 8140 KB Output is correct
23 Correct 31 ms 8312 KB Output is correct
24 Correct 60 ms 8288 KB Output is correct
25 Correct 127 ms 8328 KB Output is correct
26 Correct 105 ms 8304 KB Output is correct
27 Correct 82 ms 15892 KB Output is correct
28 Correct 2750 ms 15688 KB Output is correct
29 Correct 2615 ms 16068 KB Output is correct
30 Correct 2585 ms 14864 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 15940 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 4 ms 8012 KB Output is correct
5 Correct 14 ms 8268 KB Output is correct
6 Correct 14 ms 8268 KB Output is correct
7 Correct 14 ms 8308 KB Output is correct
8 Correct 185 ms 15932 KB Output is correct
9 Correct 183 ms 15872 KB Output is correct
10 Correct 170 ms 14540 KB Output is correct
11 Execution timed out 3078 ms 15304 KB Time limit exceeded
12 Halted 0 ms 0 KB -