Submission #718078

#	Time	Username	Problem	Language	Result	Execution time	Memory
718078		Johann	Toll (BOI17_toll)	C++14	49 / 100	3043 ms	7856 KiB

toll

// Gets sub1-sub4 with more or less naive approach
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define vvpii vector<vpii>
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define F0R(i,n) for (int i = 0; i < (n); ++i)

const int MAXN = 50005;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int k,n,m,o;
    cin >> k >> n >> m >> o;
    vvpii adj(n);
    F0R(i,m) {
        int a,b,t;
        cin >> a >> b >> t;
        adj[a].push_back({b,t});
    }
    vi ans(o, -1);
    vvpii orders(n);
    F0R(i,o) {
        int a,b;
        cin >> a >> b;
        if (a <= b)
            orders[a].push_back({ b, i });
    }
    F0R(i,n) { sort(all(orders[i])); reverse(all(orders[i])); }

    F0R(a,n) {
        int first = a;
        vi buffer(2*k+1, INT_MAX);
        buffer[0] = 0;
        while (sz(orders[a]) > 0) {
            if (first == orders[a].back().first) {
                ans[orders[a].back().second] = (buffer[0] == INT_MAX) ? -1 : buffer[0];
                orders[a].pop_back();
            } else {
                if (buffer[0] != INT_MAX) {
                    for (pii e : adj[first]) {
                        auto [u, t] = e;
                        buffer[u - first] = min(buffer[u-first], buffer[0] + t);
                    }
                }
                for (int i = 0; i < sz(buffer)-1; ++i) swap(buffer[i], buffer[i+1]);
                buffer.back() = INT_MAX;
                ++first;
            }
        }
    }

    for (int x : ans) cout << x << "\n";
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:51:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |                         auto [u, t] = e;
      |                              ^

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