Submission #675053

#	Time	Username	Problem	Language	Result	Execution time	Memory
675053		Trent	Toll (BOI17_toll)	C++17	100 / 100	238 ms	24088 KiB

toll

#include "bits/stdc++.h"
#include <cstring>
#include <fstream>

using namespace std;

#define ll long long
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define open(s) freopen(((string) s + ".in").c_str(), "r", stdin); freopen(((string) s + ".out").c_str(), "w", stdout)
#define all(i) i.begin(), i.end()
#define boost() cin.sync_with_stdio(0); cin.tie()
typedef pair<int, int> pii;

const int MN = 5e4 + 10, MK = 5, ME = 17, INF = 5e8 + 10;
struct edge{int i, w;};
int dis[MN][ME][MK];
vector<edge> adj[MN];
int k, n, m, o;

inline int st(int a){
    return k + a / k * k;
}

signed main() {
    cin >> k >> n >> m >> o;
    forR(a, MN) forR(b, ME) forR(c, MK) dis[a][b][c] = INF;

    forR(g, m){
        int a, b, t; cin >> a >> b >> t;
        dis[a][0][b - st(a)] = t;
        adj[a].push_back({b, t});
    }
    REP(e, 1, ME) forR(i, n) forR(t, k){
        dis[i][e][t] = INF;
        forR(m, k) {
            int node = k * (i / k + (1 << (e - 1))) + m;
            if(node < n) dis[i][e][t] = min(dis[i][e][t], dis[i][e-1][m] + dis[node][e-1][t]);
        }
    }
    forR(g, o){
        int a, b; cin >> a >> b;
        int amt = b / k - a / k;
        vector<int> mi(5, INF);
        mi[a % k] = 0;
        for(int c=a / k, e = ME - 1; e >= 0; --e) if((1 << e) <= amt){
            vector<int> nex(5, INF);
            forR(st, k) forR(en, k) nex[en] = min(nex[en], mi[st] + dis[k * c + st][e][en]);
            mi.swap(nex);
            c += 1 << e;
            amt -= (1 << e);
        }
        if(mi[b % k] == INF) cout << "-1\n";
        else cout << mi[b % k] << '\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44