oj.uz

Submission #292043

# Submission time Handle Problem Language Result Execution time Memory
292043 2020-09-06T08:31:47 Z Diuven Express 20/19 (ROI19_express) C++17
89 / 100
 10000 ms 1028596 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 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 7 ms 384 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 1 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 10 ms 384 KB Output is correct
13 Correct 10 ms 384 KB Output is correct
14 Correct 10 ms 384 KB Output is correct
15 Correct 7 ms 384 KB Output is correct
16 Correct 8 ms 384 KB Output is correct
17 Correct 9 ms 384 KB Output is correct
18 Correct 9 ms 384 KB Output is correct
19 Correct 9 ms 384 KB Output is correct
20 Correct 11 ms 384 KB Output is correct
21 Correct 11 ms 384 KB Output is correct
22 Correct 11 ms 384 KB Output is correct
23 Correct 9 ms 384 KB Output is correct
24 Correct 6 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 7 ms 384 KB Output is correct
29 Correct 7 ms 384 KB Output is correct
30 Correct 7 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 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 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 12 ms 768 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 10 ms 768 KB Output is correct
14 Correct 6 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 7 ms 384 KB Output is correct
20 Correct 4 ms 360 KB Output is correct
21 Correct 4 ms 420 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 456 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 37 ms 4972 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 450 ms 34552 KB Output is correct
3 Correct 369 ms 7540 KB Output is correct
4 Correct 344 ms 4180 KB Output is correct
5 Correct 313 ms 1156 KB Output is correct
6 Correct 383 ms 11384 KB Output is correct
7 Correct 361 ms 6372 KB Output is correct
8 Correct 381 ms 11768 KB Output is correct
9 Correct 355 ms 6136 KB Output is correct
10 Correct 322 ms 11356 KB Output is correct
11 Correct 314 ms 5976 KB Output is correct
12 Correct 99 ms 524 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 7 ms 384 KB Output is correct
15 Correct 11 ms 384 KB Output is correct
16 Correct 10 ms 384 KB Output is correct
17 Correct 26 ms 384 KB Output is correct
18 Correct 127 ms 1032 KB Output is correct
19 Correct 19 ms 384 KB Output is correct
20 Correct 38 ms 384 KB Output is correct
21 Correct 60 ms 384 KB Output is correct
22 Correct 49 ms 412 KB Output is correct
23 Correct 312 ms 50424 KB Output is correct
24 Correct 838 ms 144632 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 37496 KB Output is correct
2 Correct 749 ms 13184 KB Output is correct
3 Correct 731 ms 6976 KB Output is correct
4 Correct 702 ms 2156 KB Output is correct
5 Correct 551 ms 888 KB Output is correct
6 Correct 579 ms 1708 KB Output is correct
7 Correct 579 ms 20088 KB Output is correct
8 Correct 542 ms 10328 KB Output is correct
9 Correct 447 ms 16224 KB Output is correct
10 Correct 410 ms 8184 KB Output is correct
11 Correct 557 ms 20092 KB Output is correct
12 Correct 527 ms 10328 KB Output is correct
13 Correct 181 ms 640 KB Output is correct
14 Correct 13 ms 512 KB Output is correct
15 Correct 11 ms 844 KB Output is correct
16 Correct 8606 ms 1027380 KB Output is correct
17 Correct 8201 ms 1028500 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 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 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 4 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 564 KB Output is correct
18 Correct 8 ms 896 KB Output is correct
19 Correct 3 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 4 ms 384 KB Output is correct
35 Correct 4 ms 384 KB Output is correct
36 Correct 5 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 17 ms 2368 KB Output is correct
44 Correct 29 ms 2936 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 9800 KB Output is correct
2 Correct 1532 ms 41204 KB Output is correct
3 Correct 816 ms 47904 KB Output is correct
4 Correct 569 ms 1396 KB Output is correct
5 Correct 478 ms 1700 KB Output is correct
6 Correct 449 ms 1060 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 1 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 339 ms 1120 KB Output is correct
12 Correct 1549 ms 1384 KB Output is correct
13 Correct 655 ms 1160 KB Output is correct
14 Correct 418 ms 1512 KB Output is correct
15 Correct 1416 ms 1400 KB Output is correct
16 Correct 425 ms 2816 KB Output is correct
17 Correct 1284 ms 21572 KB Output is correct
18 Correct 6358 ms 15952 KB Output is correct
19 Correct 1843 ms 11260 KB Output is correct
20 Correct 221 ms 988 KB Output is correct
21 Correct 2694 ms 223484 KB Output is correct
22 Correct 591 ms 38968 KB Output is correct
23 Correct 651 ms 49788 KB Output is correct
24 Correct 606 ms 55684 KB Output is correct
25 Correct 1705 ms 239680 KB Output is correct
26 Correct 764 ms 78712 KB Output is correct
27 Correct 3064 ms 526072 KB Output is correct
28 Correct 277 ms 632 KB Output is correct
29 Correct 580 ms 55768 KB Output is correct
30 Correct 416 ms 35684 KB Output is correct
31 Correct 129 ms 772 KB Output is correct
32 Correct 160 ms 1100 KB Output is correct
33 Correct 131 ms 780 KB Output is correct
34 Correct 243 ms 1296 KB Output is correct
35 Correct 505 ms 19052 KB Output is correct
36 Correct 486 ms 18776 KB Output is correct
37 Correct 504 ms 19104 KB Output is correct
38 Correct 497 ms 18744 KB Output is correct
39 Correct 7906 ms 1028596 KB Output is correct
40 Correct 8400 ms 1027932 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 9912 KB Output is correct
2 Correct 1480 ms 41208 KB Output is correct
3 Correct 796 ms 48004 KB Output is correct
4 Correct 513 ms 1756 KB Output is correct
5 Correct 465 ms 1016 KB Output is correct
6 Correct 457 ms 888 KB Output is correct
7 Correct 423 ms 1392 KB Output is correct
8 Correct 414 ms 1056 KB Output is correct
9 Correct 621 ms 11836 KB Output is correct
10 Correct 647 ms 9608 KB Output is correct
11 Correct 668 ms 11940 KB Output is correct
12 Correct 594 ms 9040 KB Output is correct
13 Correct 591 ms 11824 KB Output is correct
14 Correct 587 ms 9536 KB Output is correct
15 Correct 245 ms 664 KB Output is correct
16 Correct 204 ms 632 KB Output is correct
17 Correct 176 ms 576 KB Output is correct
18 Correct 65 ms 432 KB Output is correct
19 Correct 496 ms 920 KB Output is correct
20 Correct 497 ms 824 KB Output is correct
21 Correct 424 ms 760 KB Output is correct
22 Correct 647 ms 156768 KB Output is correct
23 Correct 951 ms 265756 KB Output is correct
24 Correct 681 ms 5464 KB Output is correct
25 Correct 8524 ms 1028504 KB Output is correct
26 Correct 8597 ms 1028224 KB Output is correct
27 Correct 15 ms 640 KB Output is correct
28 Correct 62 ms 1252 KB Output is correct
29 Correct 155 ms 2116 KB Output is correct
30 Correct 267 ms 3004 KB Output is correct
31 Correct 425 ms 3972 KB Output is correct
32 Correct 628 ms 6032 KB Output is correct
33 Correct 867 ms 7604 KB Output is correct
34 Correct 185 ms 2920 KB Output is correct
35 Correct 762 ms 5832 KB Output is correct
36 Correct 1723 ms 7932 KB Output is correct
37 Correct 3106 ms 12248 KB Output is correct
38 Correct 4867 ms 14580 KB Output is correct
39 Correct 7044 ms 17384 KB Output is correct
40 Correct 9563 ms 24820 KB Output is correct
41 Execution timed out 10006 ms 25088 KB Time limit exceeded