Submission #203632

#	Time	Username	Problem	Language	Result	Execution time	Memory
203632		karma	Toll (BOI17_toll)	C++14	100 / 100	256 ms	18680 KiB

toll

#include<bits/stdc++.h>
#define ll            long long
#define pb            emplace_back
#define fi            first
#define se            second
#define mp            make_pair
//#define int           int64_t

using namespace std;

typedef pair<int, int> pii;
const int N = (int)5e4 + 2;
const int inf = 1e9;

int res, k, lim, n, m, o, u, v, t;
int l[N << 2], h[N << 2];
struct TNode {
    vector< vector<int> > dis;
    TNode() {}
    TNode(int k, int c): dis(k, vector<int>(k, c)) {}
    void print() {
        for(int i = 0; i < k; ++i) {
            for(int j = 0; j < k; ++j) {
                cout << (dis[i][j] == inf? -1: dis[i][j]) << ' ';
            }
            cout << '\n';
        }
    }
} st[N << 2], cost[N];
TNode ans;

bool minimize(int& a, int b) {
    if(a <= b) return 0;
    a = b; return 1;
}

TNode combine(const TNode& lef, const TNode& rig) {
    if(lef.dis[0][0] == -1) return rig;
    if(rig.dis[0][0] == -1) return lef;
    TNode res = TNode(k, inf);
    for(int i = 0; i < k; ++i) {
        for(int j = 0; j < k; ++j) {
            for(int l = 0; l < k; ++l) {
                minimize(res.dis[i][j], lef.dis[i][l] + rig.dis[l][j]);
            }
        }
    }
    return res;
}

void build(int x, int low, int high) {
    l[x] = low, h[x] = high, st[x] = TNode(k, inf);
    if(l[x] == h[x]) {
       st[x] = cost[low];
       return;
    }
    int mid = (low + high) >> 1;
    build(x << 1, low, mid);
    build(x << 1 | 1, mid + 1, high);
    st[x] = combine(st[x << 1], st[x << 1 | 1]);
}

TNode get(int x, int low, int high) {
    if(l[x] > high || h[x] < low) return TNode(k, -1);
    if(l[x] >= low && h[x] <= high) return st[x];
    return combine(get(x << 1, low, high), get(x << 1 | 1, low, high));
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define FileName      "test"
    if(fopen(FileName".inp", "r")) {
       freopen(FileName".inp", "r", stdin);
       freopen(FileName".out", "w", stdout);
    }
    cin >> k >> n >> m >> o; lim = n / k + 1;
    for(int i = 0; i <= lim; ++i) cost[i] = TNode(k, inf);
    for(int i = 1; i <= m; ++i) {
        cin >> u >> v >> t;
        minimize(cost[u / k].dis[u % k][v % k], t);
    }
    build(1, 0, lim);
    while(o --) {
        cin >> u >> v;
        if(u / k == v / k) {cout << "-1\n"; continue;}
        ans = get(1, u / k, v / k - 1);
        res = ans.dis[u % k][v % k];
        if(res == inf) cout << "-1\n";
        else cout << res << '\n';
    }
}

Compilation message (stderr)

toll.cpp: In function 'int32_t main()':
toll.cpp:74:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".inp", "r", stdin);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:75:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".out", "w", stdout);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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