oj.uz

Submission #292029

# Submission time Handle Problem Language Result Execution time Memory
292029 2020-09-06T08:23:13 Z Diuven Express 20/19 (ROI19_express) C++17
100 / 100
 1162 ms 265896 KB 
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int ll;
typedef long double ld;

const int INF = 1000 * 1000 * 1000 + 21;
const ll LLINF = (1ll << 60) + 5;
const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX_N = 500 * 1000 + 228;
const ll MAX_K = 200ll * 1000ll * 1000ll * 1000ll * 1000ll * 1000ll;

int n, m, q;
ll a;
vector<pair<int, ll>> g[MAX_N];
vector<pair<ll, ll>> segs[MAX_N];
char ans[MAX_N];

bool inter(pair<ll, ll> fr, pair<ll, ll> sc) {
    return !((fr.second < sc.first) ||  (sc.second < fr.first));
}

void add_seg(vector<pair<ll, ll>>& segs, pair<ll, ll> seg) {
    if (segs.empty() || !inter(segs.back(), seg)) {
        segs.push_back(seg);
    } else {
        pair<ll, ll> cur = {min(seg.first, segs.back().first), max(seg.second, segs.back().second)};
        segs.pop_back();
        segs.push_back(cur);
    }
}

void fix_segs(vector<pair<ll, ll>>& segs) {
    vector<pair<ll, ll>> new_segs;

    for (int i = 0; i < (int)segs.size(); ++i) {
        segs[i].first = min(segs[i].first, MAX_K);
        segs[i].second = min(segs[i].second, MAX_K);
        if (!new_segs.empty() && new_segs.back().second * a / (a - 1) >= segs[i].first) {
            pair<ll, ll> new_seg = {new_segs.back().first, segs[i].second};
            new_segs.pop_back();
            new_segs.push_back(new_seg);
        } else {
            new_segs.push_back(segs[i]);
        }
    }

    segs.swap(new_segs);
}

void add_segs(int v, int u, ll to_add) {
    for (int i = 0; i < (int)segs[v].size(); ++i) {
        segs[v][i].first += to_add;
        segs[v][i].second += to_add;
    }

    vector<pair<ll, ll>> new_segs;

    int ptr1 = 0;
    int ptr2 = 0;

    while (ptr1 < (int)segs[v].size() || ptr2 < (int)segs[u].size()) {
        if (ptr1 < (int)segs[v].size() && ptr2 < (int)segs[u].size()) {
            if (segs[v][ptr1].first < segs[u][ptr2].first) {
                add_seg(new_segs, segs[v][ptr1++]);
            } else {
                add_seg(new_segs, segs[u][ptr2++]);
            }
        } else if (ptr1 < (int)segs[v].size()) {
            add_seg(new_segs, segs[v][ptr1++]);
        } else if (ptr2 < (int)segs[u].size()) {
            add_seg(new_segs, segs[u][ptr2++]);
        } else {
            assert(false);
        }
    }

    fix_segs(new_segs);

    segs[u].swap(new_segs);

    for (int i = 0; i < (int)segs[v].size(); ++i) {
        segs[v][i].first -= to_add;
        segs[v][i].second -= to_add;
    }
}

bool get(int v, ll k) {
    pair<ll, ll> now = {k, k * a / (a - 1)};

    for (int i = 0; i < (int)segs[v].size(); ++i) {
        if (inter(now, segs[v][i])) {
            return true;
        }
    }

    return false;
}

void solve() {
    scanf("%d%d%d%lld", &n, &m, &q, &a);

    for (int i = 0; i < n; ++i) {
        g[i].clear();
        segs[i].clear();
    }

    for (int i = 0; i < m; ++i) {
        int v, u;
        ll x;
        scanf("%d%d%lld", &v, &u, &x);
        --v; --u;
        g[v].push_back({u, x});
    }

    segs[0].push_back({0, 0});
    for (int i = 0; i < n; ++i) {
        if (segs[i].empty()) {
            continue;
        }

        for (int j = 0; j < (int)g[i].size(); ++j) {
            add_segs(i, g[i][j].first, g[i][j].second);
        }
    }

    for (int i = 0; i < q; ++i) {
        int v;
        ll k;
        scanf("%d%lld", &v, &k);
        --v;
        ans[i] = '0' + get(v, k);
    }

    ans[q] = '\0';
    printf("%s\n", ans);
}

int main() {
#ifdef CH_EGOR
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif

    int t;
    scanf("%d", &t);

    while (t--) {
        solve();
    }

    return 0;
}

Compilation message

main.cpp:19: warning: ignoring #pragma comment  [-Wunknown-pragmas]
   19 | #pragma comment(linker, "/STACK:256000000")
      | 
main.cpp: In function 'void solve()':
main.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |     scanf("%d%d%d%lld", &n, &m, &q, &a);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |         scanf("%d%d%lld", &v, &u, &x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |         scanf("%d%lld", &v, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp: In function 'int main()':
main.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  169 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 17 ms 23808 KB Output is correct
8 Correct 17 ms 23808 KB Output is correct
9 Correct 17 ms 23808 KB Output is correct
10 Correct 21 ms 23936 KB Output is correct
11 Correct 23 ms 24064 KB Output is correct
12 Correct 22 ms 24064 KB Output is correct
13 Correct 22 ms 24064 KB Output is correct
14 Correct 21 ms 23936 KB Output is correct
15 Correct 19 ms 23808 KB Output is correct
16 Correct 20 ms 23808 KB Output is correct
17 Correct 21 ms 23808 KB Output is correct
18 Correct 20 ms 23808 KB Output is correct
19 Correct 20 ms 23808 KB Output is correct
20 Correct 20 ms 23808 KB Output is correct
21 Correct 21 ms 23896 KB Output is correct
22 Correct 21 ms 24192 KB Output is correct
23 Correct 25 ms 24192 KB Output is correct
24 Correct 19 ms 23936 KB Output is correct
25 Correct 21 ms 23808 KB Output is correct
26 Correct 20 ms 23936 KB Output is correct
27 Correct 20 ms 23936 KB Output is correct
28 Correct 18 ms 23808 KB Output is correct
29 Correct 20 ms 23808 KB Output is correct
30 Correct 19 ms 23808 KB Output is correct
31 Correct 19 ms 23880 KB Output is correct
32 Correct 21 ms 24192 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 494 ms 44064 KB Output is correct
3 Correct 384 ms 27896 KB Output is correct
4 Correct 351 ms 25852 KB Output is correct
5 Correct 300 ms 24312 KB Output is correct
6 Correct 391 ms 30456 KB Output is correct
7 Correct 370 ms 27256 KB Output is correct
8 Correct 403 ms 30456 KB Output is correct
9 Correct 353 ms 27128 KB Output is correct
10 Correct 367 ms 30456 KB Output is correct
11 Correct 329 ms 27128 KB Output is correct
12 Correct 106 ms 23936 KB Output is correct
13 Correct 23 ms 23808 KB Output is correct
14 Correct 22 ms 23808 KB Output is correct
15 Correct 26 ms 23808 KB Output is correct
16 Correct 26 ms 23808 KB Output is correct
17 Correct 38 ms 23808 KB Output is correct
18 Correct 129 ms 24252 KB Output is correct
19 Correct 36 ms 23808 KB Output is correct
20 Correct 50 ms 23808 KB Output is correct
21 Correct 51 ms 23808 KB Output is correct
22 Correct 73 ms 23808 KB Output is correct
23 Correct 187 ms 33272 KB Output is correct
24 Correct 373 ms 47436 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 44988 KB Output is correct
2 Correct 574 ms 28480 KB Output is correct
3 Correct 566 ms 26376 KB Output is correct
4 Correct 543 ms 24716 KB Output is correct
5 Correct 465 ms 24312 KB Output is correct
6 Correct 511 ms 24664 KB Output is correct
7 Correct 400 ms 30392 KB Output is correct
8 Correct 394 ms 27128 KB Output is correct
9 Correct 397 ms 30584 KB Output is correct
10 Correct 370 ms 27132 KB Output is correct
11 Correct 373 ms 30456 KB Output is correct
12 Correct 322 ms 27256 KB Output is correct
13 Correct 105 ms 23936 KB Output is correct
14 Correct 22 ms 23808 KB Output is correct
15 Correct 24 ms 23936 KB Output is correct
16 Correct 620 ms 81016 KB Output is correct
17 Correct 646 ms 89848 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23804 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 19 ms 23808 KB Output is correct
5 Correct 20 ms 24064 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 18 ms 23808 KB Output is correct
8 Correct 20 ms 24320 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 19 ms 23800 KB Output is correct
11 Correct 20 ms 23808 KB Output is correct
12 Correct 20 ms 23808 KB Output is correct
13 Correct 18 ms 23808 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 18 ms 23808 KB Output is correct
16 Correct 18 ms 23936 KB Output is correct
17 Correct 19 ms 23936 KB Output is correct
18 Correct 19 ms 23936 KB Output is correct
19 Correct 18 ms 23936 KB Output is correct
20 Correct 18 ms 23936 KB Output is correct
21 Correct 18 ms 23936 KB Output is correct
22 Correct 20 ms 24064 KB Output is correct
23 Correct 18 ms 23936 KB Output is correct
24 Correct 20 ms 23936 KB Output is correct
25 Correct 19 ms 23936 KB Output is correct
26 Correct 18 ms 23808 KB Output is correct
27 Correct 17 ms 23808 KB Output is correct
28 Correct 18 ms 23808 KB Output is correct
29 Correct 18 ms 23808 KB Output is correct
30 Correct 21 ms 23808 KB Output is correct
31 Correct 18 ms 23808 KB Output is correct
32 Correct 17 ms 23808 KB Output is correct
33 Correct 17 ms 23808 KB Output is correct
34 Correct 21 ms 23808 KB Output is correct
35 Correct 18 ms 23808 KB Output is correct
36 Correct 18 ms 23808 KB Output is correct
37 Correct 18 ms 23808 KB Output is correct
38 Correct 18 ms 23800 KB Output is correct
39 Correct 18 ms 23808 KB Output is correct
40 Correct 18 ms 23808 KB Output is correct
41 Correct 18 ms 23808 KB Output is correct
42 Correct 16 ms 23808 KB Output is correct
43 Correct 18 ms 24064 KB Output is correct
44 Correct 17 ms 24064 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 34196 KB Output is correct
2 Correct 1014 ms 44548 KB Output is correct
3 Correct 913 ms 54408 KB Output is correct
4 Correct 684 ms 25080 KB Output is correct
5 Correct 452 ms 25204 KB Output is correct
6 Correct 432 ms 24444 KB Output is correct
7 Correct 19 ms 23808 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 54 ms 23808 KB Output is correct
10 Correct 33 ms 23936 KB Output is correct
11 Correct 440 ms 24764 KB Output is correct
12 Correct 472 ms 24312 KB Output is correct
13 Correct 616 ms 24668 KB Output is correct
14 Correct 519 ms 25464 KB Output is correct
15 Correct 537 ms 24408 KB Output is correct
16 Correct 534 ms 25856 KB Output is correct
17 Correct 753 ms 31992 KB Output is correct
18 Correct 500 ms 34684 KB Output is correct
19 Correct 474 ms 34680 KB Output is correct
20 Correct 663 ms 24460 KB Output is correct
21 Correct 641 ms 45176 KB Output is correct
22 Correct 747 ms 50336 KB Output is correct
23 Correct 764 ms 57080 KB Output is correct
24 Correct 684 ms 56536 KB Output is correct
25 Correct 658 ms 51960 KB Output is correct
26 Correct 815 ms 74608 KB Output is correct
27 Correct 625 ms 155356 KB Output is correct
28 Correct 228 ms 23936 KB Output is correct
29 Correct 677 ms 56308 KB Output is correct
30 Correct 906 ms 44832 KB Output is correct
31 Correct 61 ms 24056 KB Output is correct
32 Correct 62 ms 24056 KB Output is correct
33 Correct 70 ms 24056 KB Output is correct
34 Correct 84 ms 24064 KB Output is correct
35 Correct 266 ms 29820 KB Output is correct
36 Correct 283 ms 29688 KB Output is correct
37 Correct 276 ms 29792 KB Output is correct
38 Correct 267 ms 29688 KB Output is correct
39 Correct 644 ms 93264 KB Output is correct
40 Correct 604 ms 81272 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 34056 KB Output is correct
2 Correct 1162 ms 44584 KB Output is correct
3 Correct 946 ms 54240 KB Output is correct
4 Correct 712 ms 25576 KB Output is correct
5 Correct 675 ms 24488 KB Output is correct
6 Correct 590 ms 24440 KB Output is correct
7 Correct 494 ms 25340 KB Output is correct
8 Correct 450 ms 24460 KB Output is correct
9 Correct 777 ms 32832 KB Output is correct
10 Correct 797 ms 33296 KB Output is correct
11 Correct 719 ms 32760 KB Output is correct
12 Correct 784 ms 31760 KB Output is correct
13 Correct 689 ms 32816 KB Output is correct
14 Correct 756 ms 33404 KB Output is correct
15 Correct 361 ms 24312 KB Output is correct
16 Correct 269 ms 24152 KB Output is correct
17 Correct 245 ms 24060 KB Output is correct
18 Correct 97 ms 23888 KB Output is correct
19 Correct 482 ms 24596 KB Output is correct
20 Correct 528 ms 24440 KB Output is correct
21 Correct 526 ms 24328 KB Output is correct
22 Correct 996 ms 265868 KB Output is correct
23 Correct 965 ms 265896 KB Output is correct
24 Correct 597 ms 28220 KB Output is correct
25 Correct 663 ms 95096 KB Output is correct
26 Correct 787 ms 100988 KB Output is correct
27 Correct 28 ms 23936 KB Output is correct
28 Correct 68 ms 24312 KB Output is correct
29 Correct 92 ms 25052 KB Output is correct
30 Correct 135 ms 25848 KB Output is correct
31 Correct 216 ms 26844 KB Output is correct
32 Correct 278 ms 27896 KB Output is correct
33 Correct 404 ms 29688 KB Output is correct
34 Correct 35 ms 24704 KB Output is correct
35 Correct 87 ms 25848 KB Output is correct
36 Correct 159 ms 27264 KB Output is correct
37 Correct 242 ms 28952 KB Output is correct
38 Correct 366 ms 30556 KB Output is correct
39 Correct 541 ms 32632 KB Output is correct
40 Correct 704 ms 34940 KB Output is correct
41 Correct 735 ms 35372 KB Output is correct