Submission #135824

#	Time	Username	Problem	Language	Result	Execution time	Memory
135824		popovicirobert	Toll (BOI17_toll)	C++14	100 / 100	247 ms	13176 KiB

toll

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44


/*const int MOD = (int) 1e9 + 7;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;

const int MAXN = 50000;
const int INF = 1e9;

vector < pair <int, int> > gl[MAXN + 1], gr[MAXN + 1];
vector < pair <int, int> > qry[MAXN + 1];

int a[MAXN + 1], b[MAXN + 1];
int dpl[MAXN + 1], dpr[MAXN + 1];
int sol[MAXN + 1], k;

void divide(int l, int r) {
    if(l == r) {
        return ;
    }

    int mid = (l + r) / 2;

    for(int nod = max(mid - k, l); nod <= min(mid + k, r); nod++) {
        dpr[nod] = 0;
        for(int i = nod + 1; i <= r; i++) {
            dpr[i] = INF;
            for(auto it : gr[i]) {
                if(it.first >= nod) {
                    dpr[i] = min(dpr[i], dpr[it.first] + it.second);
                }
            }
        }

        dpl[nod] = 0;
        for(int i = nod - 1; i >= l; i--) {
            dpl[i] = INF;
            for(auto it : gl[i]) {
                if(it.first <= nod) {
                    dpl[i] = min(dpl[i], dpl[it.first] + it.second);
                }
            }
        }

        for(int i = l; i <= nod; i++) {
            int pos = (int) qry[i].size() - 1;
            while(pos >= 0 && qry[i][pos].first >= nod) {
                sol[qry[i][pos].second] = min(sol[qry[i][pos].second], dpl[i] + dpr[qry[i][pos].first]);
                pos--;
            }
        }
    }

    for(int i = l; i <= mid; i++) {
        while(qry[i].size() && qry[i].back().first > mid) {
            qry[i].pop_back();
        }
    }

    divide(l, mid);
    divide(mid + 1, r);
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, o;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> k >> n >> m >> o;

    for(i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x++, y++;
        gr[y].push_back({x, z});
        gl[x].push_back({y, z});
    }

    for(i = 1; i <= o; i++) {
        cin >> a[i] >> b[i];
        a[i]++, b[i]++;
        qry[a[i]].push_back({b[i], i});
        sol[i] = INF;
    }

    for(i = 1; i <= n; i++) {
        sort(qry[i].begin(), qry[i].end());
    }

    divide(1, n);

    for(i = 1; i <= o; i++) {
        if(sol[i] == INF) {
            sol[i] = -1;
        }
        cout << sol[i] << "\n";
    }

    return 0;
}

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