oj.uz

Submission #292048

# Submission time Handle Problem Language Result Execution time Memory
292048 2020-09-06T08:35:22 Z Diuven Express 20/19 (ROI19_express) C++17
100 / 100
 10162 ms 1028528 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 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 1 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 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 288 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 8 ms 384 KB Output is correct
14 Correct 8 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 512 KB Output is correct
18 Correct 8 ms 384 KB Output is correct
19 Correct 7 ms 384 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 6 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 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 6 ms 384 KB Output is correct
29 Correct 6 ms 384 KB Output is correct
30 Correct 6 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 512 KB Output is correct
6 Correct 1 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 1 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 9 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 5 ms 384 KB Output is correct
18 Correct 3 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 5 ms 384 KB Output is correct
22 Correct 5 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 3 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 39 ms 4972 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 453 ms 34656 KB Output is correct
3 Correct 348 ms 7600 KB Output is correct
4 Correct 354 ms 4060 KB Output is correct
5 Correct 301 ms 1300 KB Output is correct
6 Correct 366 ms 11512 KB Output is correct
7 Correct 339 ms 6264 KB Output is correct
8 Correct 381 ms 11740 KB Output is correct
9 Correct 345 ms 6260 KB Output is correct
10 Correct 348 ms 11356 KB Output is correct
11 Correct 311 ms 6108 KB Output is correct
12 Correct 97 ms 512 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 7 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 128 ms 1076 KB Output is correct
19 Correct 19 ms 384 KB Output is correct
20 Correct 39 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 309 ms 50168 KB Output is correct
24 Correct 833 ms 144248 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 37428 KB Output is correct
2 Correct 765 ms 12996 KB Output is correct
3 Correct 744 ms 7128 KB Output is correct
4 Correct 699 ms 2424 KB Output is correct
5 Correct 542 ms 1020 KB Output is correct
6 Correct 595 ms 1496 KB Output is correct
7 Correct 580 ms 20088 KB Output is correct
8 Correct 553 ms 10316 KB Output is correct
9 Correct 439 ms 16224 KB Output is correct
10 Correct 408 ms 8184 KB Output is correct
11 Correct 570 ms 20088 KB Output is correct
12 Correct 540 ms 10312 KB Output is correct
13 Correct 196 ms 632 KB Output is correct
14 Correct 16 ms 384 KB Output is correct
15 Correct 11 ms 844 KB Output is correct
16 Correct 8435 ms 1027368 KB Output is correct
17 Correct 8057 ms 1028520 KB Output is correct

Subtask #5
11.0 / 11.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 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 7 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 4 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 1024 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 4 ms 384 KB Output is correct
35 Correct 4 ms 384 KB Output is correct
36 Correct 4 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 5 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 2424 KB Output is correct
44 Correct 18 ms 2944 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 9772 KB Output is correct
2 Correct 1487 ms 41336 KB Output is correct
3 Correct 813 ms 47992 KB Output is correct
4 Correct 564 ms 1624 KB Output is correct
5 Correct 432 ms 1572 KB Output is correct
6 Correct 413 ms 1120 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 31 ms 384 KB Output is correct
10 Correct 13 ms 384 KB Output is correct
11 Correct 357 ms 1192 KB Output is correct
12 Correct 1483 ms 1380 KB Output is correct
13 Correct 645 ms 1232 KB Output is correct
14 Correct 416 ms 1388 KB Output is correct
15 Correct 1371 ms 1496 KB Output is correct
16 Correct 395 ms 2504 KB Output is correct
17 Correct 1290 ms 21504 KB Output is correct
18 Correct 6410 ms 15944 KB Output is correct
19 Correct 1851 ms 11368 KB Output is correct
20 Correct 221 ms 1020 KB Output is correct
21 Correct 2541 ms 223608 KB Output is correct
22 Correct 549 ms 39032 KB Output is correct
23 Correct 647 ms 49656 KB Output is correct
24 Correct 587 ms 55672 KB Output is correct
25 Correct 1638 ms 239936 KB Output is correct
26 Correct 769 ms 78584 KB Output is correct
27 Correct 2988 ms 526208 KB Output is correct
28 Correct 283 ms 632 KB Output is correct
29 Correct 584 ms 55632 KB Output is correct
30 Correct 409 ms 35680 KB Output is correct
31 Correct 126 ms 772 KB Output is correct
32 Correct 157 ms 1024 KB Output is correct
33 Correct 129 ms 876 KB Output is correct
34 Correct 242 ms 1252 KB Output is correct
35 Correct 493 ms 18772 KB Output is correct
36 Correct 504 ms 18908 KB Output is correct
37 Correct 499 ms 18748 KB Output is correct
38 Correct 502 ms 18896 KB Output is correct
39 Correct 7949 ms 1028528 KB Output is correct
40 Correct 8364 ms 1027848 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 9796 KB Output is correct
2 Correct 1473 ms 41488 KB Output is correct
3 Correct 803 ms 47952 KB Output is correct
4 Correct 510 ms 1936 KB Output is correct
5 Correct 463 ms 1016 KB Output is correct
6 Correct 448 ms 1016 KB Output is correct
7 Correct 418 ms 1412 KB Output is correct
8 Correct 371 ms 1132 KB Output is correct
9 Correct 614 ms 11804 KB Output is correct
10 Correct 594 ms 9516 KB Output is correct
11 Correct 603 ms 11832 KB Output is correct
12 Correct 574 ms 9100 KB Output is correct
13 Correct 551 ms 11868 KB Output is correct
14 Correct 542 ms 9632 KB Output is correct
15 Correct 245 ms 632 KB Output is correct
16 Correct 200 ms 540 KB Output is correct
17 Correct 176 ms 632 KB Output is correct
18 Correct 66 ms 384 KB Output is correct
19 Correct 491 ms 888 KB Output is correct
20 Correct 500 ms 888 KB Output is correct
21 Correct 420 ms 760 KB Output is correct
22 Correct 633 ms 156792 KB Output is correct
23 Correct 907 ms 265784 KB Output is correct
24 Correct 652 ms 5408 KB Output is correct
25 Correct 8439 ms 1028208 KB Output is correct
26 Correct 8452 ms 1028104 KB Output is correct
27 Correct 15 ms 640 KB Output is correct
28 Correct 64 ms 1244 KB Output is correct
29 Correct 153 ms 2104 KB Output is correct
30 Correct 262 ms 2892 KB Output is correct
31 Correct 423 ms 3856 KB Output is correct
32 Correct 628 ms 5728 KB Output is correct
33 Correct 859 ms 7636 KB Output is correct
34 Correct 190 ms 2988 KB Output is correct
35 Correct 770 ms 5824 KB Output is correct
36 Correct 1728 ms 8016 KB Output is correct
37 Correct 3133 ms 12084 KB Output is correct
38 Correct 4897 ms 14632 KB Output is correct
39 Correct 6946 ms 17108 KB Output is correct
40 Correct 9476 ms 24320 KB Output is correct
41 Correct 10162 ms 24964 KB Output is correct