oj.uz

Submission #480710

# Submission time Handle Problem Language Result Execution time Memory
480710 2021-10-17T23:07:44 Z hidden1 Toll (BOI17_toll) C++14
8 / 100
 3000 ms 14660 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));
    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];

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);
            }
        }
    }
    while(q --) {
        ll a, b;
        cin >> a >> b;
        if(a / k >= b / k) {
            cout << -1 << endl; 
            continue;
        } 
        mat ret = prec[a / k];
        a += k;
        while(a / k < b / k) {
            ret = mult(ret, prec[a / k]);
            a += k;
        }
        if(ret[a % k][b % k] == mod) {
            cout << -1 << endl; 
        } else {
            cout << ret[a % k][b % k] << endl;
        }
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 10596 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 3052 ms 12056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 8 ms 5068 KB Output is correct
7 Correct 7 ms 5068 KB Output is correct
8 Correct 14 ms 5256 KB Output is correct
9 Correct 10 ms 5196 KB Output is correct
10 Correct 209 ms 10360 KB Output is correct
11 Correct 225 ms 11884 KB Output is correct
12 Correct 261 ms 13508 KB Output is correct
13 Correct 287 ms 14660 KB Output is correct
14 Correct 249 ms 12488 KB Output is correct
15 Correct 238 ms 10276 KB Output is correct
16 Correct 217 ms 10180 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 8 ms 5068 KB Output is correct
7 Correct 7 ms 5068 KB Output is correct
8 Correct 14 ms 5256 KB Output is correct
9 Correct 10 ms 5196 KB Output is correct
10 Correct 209 ms 10360 KB Output is correct
11 Correct 225 ms 11884 KB Output is correct
12 Correct 261 ms 13508 KB Output is correct
13 Correct 287 ms 14660 KB Output is correct
14 Correct 249 ms 12488 KB Output is correct
15 Correct 238 ms 10276 KB Output is correct
16 Correct 217 ms 10180 KB Output is correct
17 Execution timed out 3084 ms 12016 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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