Submission #292048

#	Time	Username	Problem	Language	Result	Execution time	Memory
292048		Diuven	Express 20/19 (ROI19_express)	C++17	100 / 100	10162 ms	1028528 KiB

express

// Dmitry _kun_ Sayutin (2019)

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;
using std::swap;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

struct edge_t {
    int to;
    int64_t w;
};

void solve() {
    int n, m, q, p;
    cin >> n >> m >> q >> p;

    vector<vector<edge_t>> graph(n);
    for (int i = 0; i != m; ++i) {
        int v = input<int>() - 1;
        int u = input<int>() - 1;
        int64_t w = input<int64_t>();

        graph[u].push_back(edge_t {v, w});
    }

    vector<vector<int64_t>> segms(n);
    segms[0] = {0};

    for (int v = 1; v != n; ++v) {
        vector<int64_t> lst;
        
        for (auto u: graph[v])
            for (int64_t val: segms[u.to])
                lst.push_back(val + u.w);

        sort(ALL(lst));
        lst.resize(std::unique(ALL(lst)) - lst.begin());
        reverse(ALL(lst));

        for (int64_t elem: lst) {
            while (segms[v].size() >= 2 and p * elem > (p - 1) * segms[v][SZ(segms[v]) - 2])
                segms[v].pop_back();

            segms[v].push_back(elem);
        }

        assert(segms[v].size() <= 1500);
    }

    for (; q != 0; --q) {
        int v = input<int>() - 1;
        int64_t w = input<int64_t>();

        bool ok = false;
        for (int64_t len: segms[v])
            if (w <= len and len * (p - 1) <= w * p) {
                ok = true;
                break;
            }

        cout << (ok ? '1' : '0');
    }

    cout << "\n";
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    for (int t = input<int>(); t != 0; --t)
        solve();
    
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 24 / 24
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11