Submission #386566

#	Time	Username	Problem	Language	Result	Execution time	Memory
386566		jeroenodb	Toll (BOI17_toll)	C++14	100 / 100	241 ms	17516 KiB

toll

#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 = 5e4+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: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44