oj.uz

Submission #292040

# Submission time Handle Problem Language Result Execution time Memory
292040 2020-09-06T08:30:42 Z Diuven Express 20/19 (ROI19_express) C++17
67 / 100
 3000 ms 405460 KB 
// 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 388 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 380 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 8 ms 384 KB Output is correct
14 Correct 9 ms 384 KB Output is correct
15 Correct 7 ms 384 KB Output is correct
16 Correct 7 ms 384 KB Output is correct
17 Correct 7 ms 384 KB Output is correct
18 Correct 9 ms 384 KB Output is correct
19 Correct 7 ms 512 KB Output is correct
20 Correct 8 ms 384 KB Output is correct
21 Correct 7 ms 384 KB Output is correct
22 Correct 7 ms 384 KB Output is correct
23 Correct 8 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 8 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 11 ms 768 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
13 Correct 7 ms 768 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 768 KB Output is correct
23 Correct 5 ms 768 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 4 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 3 ms 384 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 37 ms 4980 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 445 ms 34472 KB Output is correct
3 Correct 355 ms 7568 KB Output is correct
4 Correct 332 ms 3932 KB Output is correct
5 Correct 303 ms 1156 KB Output is correct
6 Correct 354 ms 11512 KB Output is correct
7 Correct 339 ms 6264 KB Output is correct
8 Correct 374 ms 11740 KB Output is correct
9 Correct 337 ms 6136 KB Output is correct
10 Correct 333 ms 11356 KB Output is correct
11 Correct 311 ms 5984 KB Output is correct
12 Correct 99 ms 512 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 8 ms 384 KB Output is correct
15 Correct 10 ms 384 KB Output is correct
16 Correct 10 ms 384 KB Output is correct
17 Correct 24 ms 384 KB Output is correct
18 Correct 131 ms 1036 KB Output is correct
19 Correct 19 ms 384 KB Output is correct
20 Correct 43 ms 384 KB Output is correct
21 Correct 39 ms 384 KB Output is correct
22 Correct 39 ms 384 KB Output is correct
23 Correct 312 ms 50168 KB Output is correct
24 Correct 857 ms 144292 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 37364 KB Output is correct
2 Correct 749 ms 12884 KB Output is correct
3 Correct 733 ms 6848 KB Output is correct
4 Correct 725 ms 2092 KB Output is correct
5 Correct 582 ms 1052 KB Output is correct
6 Correct 580 ms 1612 KB Output is correct
7 Correct 585 ms 20024 KB Output is correct
8 Correct 583 ms 10264 KB Output is correct
9 Correct 454 ms 16220 KB Output is correct
10 Correct 416 ms 8324 KB Output is correct
11 Correct 559 ms 20188 KB Output is correct
12 Correct 527 ms 10232 KB Output is correct
13 Correct 182 ms 632 KB Output is correct
14 Correct 13 ms 384 KB Output is correct
15 Correct 14 ms 844 KB Output is correct
16 Execution timed out 3107 ms 405460 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 6 ms 1408 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 5 ms 512 KB Output is correct
18 Correct 6 ms 896 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 6 ms 896 KB Output is correct
21 Correct 7 ms 1152 KB Output is correct
22 Correct 3 ms 768 KB Output is correct
23 Correct 6 ms 896 KB Output is correct
24 Correct 5 ms 768 KB Output is correct
25 Correct 8 ms 1280 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 4 ms 384 KB Output is correct
36 Correct 3 ms 384 KB Output is correct
37 Correct 4 ms 384 KB Output is correct
38 Correct 4 ms 384 KB Output is correct
39 Correct 4 ms 384 KB Output is correct
40 Correct 4 ms 384 KB Output is correct
41 Correct 4 ms 384 KB Output is correct
42 Correct 4 ms 384 KB Output is correct
43 Correct 18 ms 2432 KB Output is correct
44 Correct 18 ms 2944 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 9736 KB Output is correct
2 Correct 1508 ms 41464 KB Output is correct
3 Correct 806 ms 47992 KB Output is correct
4 Correct 566 ms 1452 KB Output is correct
5 Correct 429 ms 1612 KB Output is correct
6 Correct 428 ms 1124 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 32 ms 384 KB Output is correct
10 Correct 13 ms 384 KB Output is correct
11 Correct 335 ms 1332 KB Output is correct
12 Correct 1466 ms 1628 KB Output is correct
13 Correct 647 ms 1152 KB Output is correct
14 Correct 418 ms 1604 KB Output is correct
15 Correct 1365 ms 1712 KB Output is correct
16 Correct 407 ms 2644 KB Output is correct
17 Correct 1283 ms 21532 KB Output is correct
18 Execution timed out 3085 ms 14052 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 9796 KB Output is correct
2 Correct 1489 ms 41340 KB Output is correct
3 Correct 864 ms 48076 KB Output is correct
4 Correct 521 ms 1952 KB Output is correct
5 Correct 464 ms 1016 KB Output is correct
6 Correct 504 ms 936 KB Output is correct
7 Correct 439 ms 1376 KB Output is correct
8 Correct 400 ms 992 KB Output is correct
9 Correct 694 ms 11756 KB Output is correct
10 Correct 669 ms 9536 KB Output is correct
11 Correct 630 ms 11880 KB Output is correct
12 Correct 634 ms 8972 KB Output is correct
13 Correct 571 ms 11860 KB Output is correct
14 Correct 664 ms 9484 KB Output is correct
15 Correct 247 ms 624 KB Output is correct
16 Correct 210 ms 632 KB Output is correct
17 Correct 187 ms 580 KB Output is correct
18 Correct 67 ms 468 KB Output is correct
19 Correct 542 ms 888 KB Output is correct
20 Correct 550 ms 764 KB Output is correct
21 Correct 450 ms 760 KB Output is correct
22 Correct 736 ms 156544 KB Output is correct
23 Correct 1039 ms 265680 KB Output is correct
24 Correct 674 ms 5316 KB Output is correct
25 Execution timed out 3052 ms 380824 KB Time limit exceeded
26 Halted 0 ms 0 KB -