oj.uz

Submission #386565

# Submission time Handle Problem Language Result Execution time Memory
386565 2021-04-06T20:31:14 Z jeroenodb Toll (BOI17_toll) C++14
0 / 100
 2 ms 768 KB 
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 5e1+1 , oo = 1e9;
int dist[17][mxN][5];
void minset(int& a, int b) {
    a = min(a,b);
}
const array<int,5> init = {oo,oo,oo,oo,oo};
int main() {
    int k,n,m,o; cin >> k >> n >> m >> o;
    for(int i=0;i<n;++i) {
        for(int j=0;j<k;++j) {
            dist[0][i][j] = oo;
        }
    }
    for(int i=0;i<m;++i) {
        int a,b,t; cin >> a >> b >> t;
        dist[0][a][b%k] = t;
    }
    int B = (n+k-1)/k;
    for(int j=1;(1<<j)<B;++j) {
        int halflen = 1<<(j-1);
        for(int a =0;a<n;++a) {
            int block = a/k;
            int delta = k*(halflen+block);
            
            for(int c=0;c<k;++c) {
                dist[j][a][c] = oo;
                for(int b=0;b<k;++b) {
                    int id = b+delta;
                    if(id>=n) break;
                    minset(dist[j][a][c], dist[j-1][a][b]+dist[j-1][id][c]);
                }
            }
        }
    }
    while(o--) {
        int a,b; cin >> a >> b;
        int id = a/k;
        int d = b/k - id;
        if(d<0) {
            cout << "-1\n";
            continue;
        }
        array<int,5> at = init,to;
        at[a%k]=0;
        for(int i=0;1<<i <= d;++i) {
            if(d&(1<<i)) {
                to = init;
                // update at table
                for(int c=0;c<k;++c)
                    for(int e=0;e<k;++e)
                        minset(to[e], at[c]+dist[i][id*k+c][e]);
                swap(to,at);
                id+=1<<i;
            }
        }
        cout << (at[b%k]==oo?-1:at[b%k]) << '\n';
    }

}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 748 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 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Runtime error 1 ms 492 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Runtime error 1 ms 492 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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