oj.uz

Submission #480711

# Submission time Handle Problem Language Result Execution time Memory
480711 2021-10-17T23:20:37 Z hidden1 Toll (BOI17_toll) C++14
46 / 100
 3000 ms 18488 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 = 500;
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 300 ms 16016 KB Output is correct
2 Correct 5 ms 8012 KB Output is correct
3 Correct 5 ms 8040 KB Output is correct
4 Correct 6 ms 8012 KB Output is correct
5 Correct 22 ms 8268 KB Output is correct
6 Correct 30 ms 8268 KB Output is correct
7 Correct 22 ms 8268 KB Output is correct
8 Correct 354 ms 16832 KB Output is correct
9 Correct 302 ms 16968 KB Output is correct
10 Correct 278 ms 14432 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8012 KB Output is correct
2 Correct 5 ms 8012 KB Output is correct
3 Correct 4 ms 8012 KB Output is correct
4 Correct 4 ms 8072 KB Output is correct
5 Correct 5 ms 8012 KB Output is correct
6 Correct 7 ms 8268 KB Output is correct
7 Correct 8 ms 8272 KB Output is correct
8 Correct 15 ms 8268 KB Output is correct
9 Correct 11 ms 8284 KB Output is correct
10 Correct 74 ms 15812 KB Output is correct
11 Correct 162 ms 15152 KB Output is correct
12 Correct 266 ms 15520 KB Output is correct
13 Correct 248 ms 15972 KB Output is correct
14 Correct 223 ms 14840 KB Output is correct
15 Correct 258 ms 12580 KB Output is correct
16 Correct 202 ms 12548 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8012 KB Output is correct
2 Correct 5 ms 8012 KB Output is correct
3 Correct 4 ms 8012 KB Output is correct
4 Correct 4 ms 8072 KB Output is correct
5 Correct 5 ms 8012 KB Output is correct
6 Correct 7 ms 8268 KB Output is correct
7 Correct 8 ms 8272 KB Output is correct
8 Correct 15 ms 8268 KB Output is correct
9 Correct 11 ms 8284 KB Output is correct
10 Correct 74 ms 15812 KB Output is correct
11 Correct 162 ms 15152 KB Output is correct
12 Correct 266 ms 15520 KB Output is correct
13 Correct 248 ms 15972 KB Output is correct
14 Correct 223 ms 14840 KB Output is correct
15 Correct 258 ms 12580 KB Output is correct
16 Correct 202 ms 12548 KB Output is correct
17 Correct 1746 ms 15296 KB Output is correct
18 Correct 5 ms 8012 KB Output is correct
19 Correct 5 ms 8116 KB Output is correct
20 Correct 6 ms 8012 KB Output is correct
21 Correct 4 ms 8112 KB Output is correct
22 Correct 5 ms 8112 KB Output is correct
23 Correct 56 ms 8268 KB Output is correct
24 Correct 55 ms 8324 KB Output is correct
25 Correct 156 ms 8380 KB Output is correct
26 Correct 113 ms 8268 KB Output is correct
27 Correct 135 ms 16780 KB Output is correct
28 Correct 2878 ms 17744 KB Output is correct
29 Correct 2713 ms 18488 KB Output is correct
30 Correct 2687 ms 16704 KB Output is correct

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 16016 KB Output is correct
2 Correct 5 ms 8012 KB Output is correct
3 Correct 5 ms 8040 KB Output is correct
4 Correct 6 ms 8012 KB Output is correct
5 Correct 22 ms 8268 KB Output is correct
6 Correct 30 ms 8268 KB Output is correct
7 Correct 22 ms 8268 KB Output is correct
8 Correct 354 ms 16832 KB Output is correct
9 Correct 302 ms 16968 KB Output is correct
10 Correct 278 ms 14432 KB Output is correct
11 Execution timed out 3069 ms 15180 KB Time limit exceeded
12 Halted 0 ms 0 KB -