Submission #999514

#	Time	Username	Problem	Language	Result	Execution time	Memory
999514		Peter2017	Toll (BOI17_toll)	C++14	0 / 100	3023 ms	20304 KiB

toll

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pill pair<int,ll>
#define mem(a, b) memset(a, b, sizeof(a))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define name "test"

using namespace std;

const int N = 5e4 + 5;
const int mod = 1e9 + 696;
const ll oo = 1e18;

template <typename T1, typename T2> bool maxi(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;}
template <typename T1, typename T2> bool mini(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;}

struct item{
    int a, b, i;
};

int k;
int n;
int m;
int q;
int ans[N];
int f[N][6][2];
vector<pii> adj1[N];
vector<pii> adj2[N];
vector <item> query[N];

void load(){
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
}

void addQuery(int id, int l, int r, int u, int v, int a, int b, int i){
    if (l > r) return;
    int m = (l + r) >> 1;
    if (u <= m && v > m){
        query[id].push_back({a, b, i});
        return;
    }
    if (m < u) addQuery(id << 1 | 1, m + 1, r, u, v, a, b, i);
    else addQuery(id << 1, l, m, u, v, a, b, i);
}

void input(){
    cin >> k >> n >> m >> q;
    for (int i = 1; i <= m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        u++; v++;
        adj1[u].push_back({v, c});
        adj2[v].push_back({u, c});
    }
    mem(ans, 0x3f);
    for (int i = 1; i <= q; i++){
        int a, b;
        cin >> a >> b;
        a++; b++;
        if (a == b) ans[i] = 0;
        addQuery(1, 0, n / k, a / k, b / k, a, b, i);
    }
}

void dnc(int id, int l, int r){
    if (l >= r) return;
    int m = (l + r) >> 1;
    int lo = max(1, l * k);
    int hi = min(n, (r + 1) * k - 1);
    for (int i = lo; i <= hi; i++){
        mem(f[i], 0x3f);
    }
    lo = max(1, m * k);
    hi = min(n, (m + 1) * k - 1);
    for (int i = lo; i <= hi; i++)
        f[i][i - lo][0] = f[i][i - lo][1] = 0;
    for (int i = lo - 1; i >= max(1, l * k); i--){
        for (int j = 0; j < k; j++){
            for (auto v : adj1[i]){
                mini(f[i][j][0], f[v.fi][j][0] + v.se);
            }
        }
    }
    for (int i = hi + 1; i <= min(n, (r + 1) * k - 1); i++){
        for (int j = 0; j < k; j++){
            for (auto v : adj2[i])
                mini(f[i][j][1], f[v.fi][j][1] + v.se);
        }
    }
    for (auto it : query[id]){
        for (int j = 0; j < k; j++){
            if (f[it.a][j][0] < mod && f[it.b][j][1] < mod){
                mini(ans[it.i], f[it.a][j][0] + f[it.b][j][1]);
            }
        }
    }
    dnc(id << 1, l, m);
    dnc(id << 1 | 1, m + 1, r);
}

void solve(){
    dnc(1, 0, n / k);
    for (int i = 1; i <= q; i++){
        if (ans[i] >= mod) ans[i] = -1;
        cout << ans[i] << '\n';
    }
}

int main(){
    load();
    input();
    solve();
}

Compilation message (stderr)

toll.cpp: In function 'void load()':
toll.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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