oj.uz

Submission #292030

# Submission time Handle Problem Language Result Execution time Memory
292030 2020-09-06T08:25:46 Z Diuven Express 20/19 (ROI19_express) C++17
100 / 100
 608 ms 265976 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;

/** Interface */

inline int readChar();
template <class T = int>
inline T readInt();
template <class T>
inline void writeInt(T x);
inline void writeChar(int x);
inline void writeWord(const char* s);
inline void flush();

/** Read */

static const int buf_size = 4096;

inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len)
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    if (pos == len)
        return -1;
    return buf[pos++];
}

inline int readChar() {
    int c = getChar();
    while (c <= 32)
        c = getChar();
    return c;
}

template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}

/** Write */

static int write_pos = 0;
static char write_buf[buf_size];

inline void writeChar(int x) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}

inline void flush() {
    if (write_pos)
        fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
}

template <class T>
inline void writeInt(T x) {
    if (x < 0)
        writeChar('-'), x = -x;

    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
}

inline void writeWord(const char* s) {
    while (*s)
        writeChar(*s++);
}

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, ll to_add) {
    return !((fr.second < sc.first + to_add) ||  (sc.second + to_add < fr.first));
}

vector<pair<ll, ll>> new_segs;
vector<pair<ll, ll>> new_segs2;

void fix_segs() {
    new_segs2.clear();

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

    new_segs.swap(new_segs2);
}

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

void add_segs(int v, int u, ll to_add) {
    new_segs.clear();

    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 + to_add < segs[u][ptr2].first) {
                add_seg(segs[v][ptr1++], to_add);
            } else {
                add_seg(segs[u][ptr2++], 0);
            }
        } else if (ptr1 < (int)segs[v].size()) {
            add_seg(segs[v][ptr1++], to_add);
        } else if (ptr2 < (int)segs[u].size()) {
            add_seg(segs[u][ptr2++], 0);
        } else {
            assert(false);
        }
    }

    fix_segs();

    segs[u].swap(new_segs);
}

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], 0)) {
            return true;
        }
    }

    return false;
}

void solve() {
    n = readInt();
    m = readInt();
    q = readInt();
    a = readInt();

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

    for (int i = 0; i < m; ++i) {
        int v = readInt() - 1;
        int u = readInt() - 1;
        ll x = readInt<ll>();
        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 = readInt() - 1;
        ll k = readInt<ll>();
        ans[i] = '0' + get(v, k);
    }

    ans[q] = '\n';
    ans[q + 1] = '\0';
    writeWord(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 = readInt();

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

    flush();

    return 0;
}

Compilation message

main.cpp:19: warning: ignoring #pragma comment  [-Wunknown-pragmas]
   19 | #pragma comment(linker, "/STACK:256000000")
      |

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 16 ms 23808 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 16 ms 23808 KB Output is correct
7 Correct 17 ms 23868 KB Output is correct
8 Correct 17 ms 23808 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 17 ms 23808 KB Output is correct
11 Correct 17 ms 23808 KB Output is correct
12 Correct 18 ms 23808 KB Output is correct
13 Correct 19 ms 23808 KB Output is correct
14 Correct 21 ms 23808 KB Output is correct
15 Correct 20 ms 23792 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 19 ms 23808 KB Output is correct
18 Correct 19 ms 23808 KB Output is correct
19 Correct 20 ms 23808 KB Output is correct
20 Correct 18 ms 23808 KB Output is correct
21 Correct 18 ms 23808 KB Output is correct
22 Correct 18 ms 23808 KB Output is correct
23 Correct 22 ms 23808 KB Output is correct
24 Correct 17 ms 23808 KB Output is correct
25 Correct 17 ms 23808 KB Output is correct
26 Correct 18 ms 23912 KB Output is correct
27 Correct 20 ms 23808 KB Output is correct
28 Correct 18 ms 23884 KB Output is correct
29 Correct 18 ms 23808 KB Output is correct
30 Correct 17 ms 23808 KB Output is correct

Subtask #2
24.0 / 24.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 16 ms 23808 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 16 ms 23808 KB Output is correct
10 Correct 20 ms 23936 KB Output is correct
11 Correct 19 ms 24064 KB Output is correct
12 Correct 18 ms 24192 KB Output is correct
13 Correct 19 ms 24064 KB Output is correct
14 Correct 19 ms 23848 KB Output is correct
15 Correct 17 ms 23808 KB Output is correct
16 Correct 17 ms 23808 KB Output is correct
17 Correct 17 ms 23936 KB Output is correct
18 Correct 17 ms 23808 KB Output is correct
19 Correct 17 ms 23808 KB Output is correct
20 Correct 19 ms 23808 KB Output is correct
21 Correct 19 ms 23808 KB Output is correct
22 Correct 20 ms 24192 KB Output is correct
23 Correct 19 ms 24320 KB Output is correct
24 Correct 19 ms 23936 KB Output is correct
25 Correct 17 ms 23936 KB Output is correct
26 Correct 18 ms 23936 KB Output is correct
27 Correct 17 ms 23936 KB Output is correct
28 Correct 17 ms 23808 KB Output is correct
29 Correct 17 ms 23808 KB Output is correct
30 Correct 17 ms 23936 KB Output is correct
31 Correct 17 ms 23936 KB Output is correct
32 Correct 21 ms 24448 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 261 ms 44024 KB Output is correct
3 Correct 121 ms 27904 KB Output is correct
4 Correct 106 ms 25856 KB Output is correct
5 Correct 63 ms 24192 KB Output is correct
6 Correct 139 ms 30456 KB Output is correct
7 Correct 95 ms 27128 KB Output is correct
8 Correct 149 ms 30456 KB Output is correct
9 Correct 100 ms 27164 KB Output is correct
10 Correct 127 ms 30480 KB Output is correct
11 Correct 114 ms 27128 KB Output is correct
12 Correct 32 ms 23912 KB Output is correct
13 Correct 17 ms 23808 KB Output is correct
14 Correct 18 ms 23784 KB Output is correct
15 Correct 18 ms 23808 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 21 ms 23808 KB Output is correct
18 Correct 37 ms 24192 KB Output is correct
19 Correct 19 ms 23808 KB Output is correct
20 Correct 22 ms 23808 KB Output is correct
21 Correct 30 ms 23800 KB Output is correct
22 Correct 22 ms 23904 KB Output is correct
23 Correct 59 ms 33324 KB Output is correct
24 Correct 119 ms 47480 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 45176 KB Output is correct
2 Correct 145 ms 28408 KB Output is correct
3 Correct 109 ms 26428 KB Output is correct
4 Correct 94 ms 24696 KB Output is correct
5 Correct 86 ms 24440 KB Output is correct
6 Correct 117 ms 24568 KB Output is correct
7 Correct 131 ms 30456 KB Output is correct
8 Correct 95 ms 27128 KB Output is correct
9 Correct 123 ms 30456 KB Output is correct
10 Correct 94 ms 27128 KB Output is correct
11 Correct 131 ms 30456 KB Output is correct
12 Correct 114 ms 27296 KB Output is correct
13 Correct 43 ms 23936 KB Output is correct
14 Correct 17 ms 23808 KB Output is correct
15 Correct 20 ms 23936 KB Output is correct
16 Correct 244 ms 81016 KB Output is correct
17 Correct 256 ms 89780 KB Output is correct

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 41368 KB Output is correct
2 Correct 434 ms 49980 KB Output is correct
3 Correct 523 ms 57372 KB Output is correct
4 Correct 191 ms 25848 KB Output is correct
5 Correct 112 ms 25592 KB Output is correct
6 Correct 109 ms 24568 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 25 ms 23808 KB Output is correct
10 Correct 20 ms 23808 KB Output is correct
11 Correct 124 ms 26232 KB Output is correct
12 Correct 117 ms 24696 KB Output is correct
13 Correct 166 ms 24824 KB Output is correct
14 Correct 146 ms 27348 KB Output is correct
15 Correct 138 ms 24828 KB Output is correct
16 Correct 112 ms 27064 KB Output is correct
17 Correct 267 ms 35452 KB Output is correct
18 Correct 153 ms 34680 KB Output is correct
19 Correct 135 ms 34680 KB Output is correct
20 Correct 186 ms 25080 KB Output is correct
21 Correct 320 ms 47992 KB Output is correct
22 Correct 378 ms 55032 KB Output is correct
23 Correct 419 ms 60540 KB Output is correct
24 Correct 308 ms 56568 KB Output is correct
25 Correct 328 ms 52472 KB Output is correct
26 Correct 460 ms 78588 KB Output is correct
27 Correct 343 ms 165212 KB Output is correct
28 Correct 66 ms 24028 KB Output is correct
29 Correct 316 ms 56184 KB Output is correct
30 Correct 561 ms 166560 KB Output is correct
31 Correct 25 ms 24064 KB Output is correct
32 Correct 25 ms 24064 KB Output is correct
33 Correct 24 ms 24064 KB Output is correct
34 Correct 30 ms 24192 KB Output is correct
35 Correct 93 ms 29816 KB Output is correct
36 Correct 82 ms 29688 KB Output is correct
37 Correct 91 ms 29780 KB Output is correct
38 Correct 79 ms 29816 KB Output is correct
39 Correct 269 ms 93176 KB Output is correct
40 Correct 245 ms 81144 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 41364 KB Output is correct
2 Correct 423 ms 49964 KB Output is correct
3 Correct 512 ms 57360 KB Output is correct
4 Correct 160 ms 27000 KB Output is correct
5 Correct 142 ms 24824 KB Output is correct
6 Correct 148 ms 24540 KB Output is correct
7 Correct 127 ms 26296 KB Output is correct
8 Correct 98 ms 24696 KB Output is correct
9 Correct 281 ms 32812 KB Output is correct
10 Correct 328 ms 39288 KB Output is correct
11 Correct 259 ms 32760 KB Output is correct
12 Correct 271 ms 34604 KB Output is correct
13 Correct 246 ms 32756 KB Output is correct
14 Correct 310 ms 39288 KB Output is correct
15 Correct 130 ms 27640 KB Output is correct
16 Correct 97 ms 25360 KB Output is correct
17 Correct 71 ms 24440 KB Output is correct
18 Correct 33 ms 24028 KB Output is correct
19 Correct 183 ms 33384 KB Output is correct
20 Correct 168 ms 28408 KB Output is correct
21 Correct 142 ms 25592 KB Output is correct
22 Correct 608 ms 265852 KB Output is correct
23 Correct 596 ms 265976 KB Output is correct
24 Correct 144 ms 29052 KB Output is correct
25 Correct 268 ms 95096 KB Output is correct
26 Correct 304 ms 100984 KB Output is correct
27 Correct 20 ms 24064 KB Output is correct
28 Correct 30 ms 24448 KB Output is correct
29 Correct 47 ms 25208 KB Output is correct
30 Correct 63 ms 26112 KB Output is correct
31 Correct 88 ms 27008 KB Output is correct
32 Correct 122 ms 28280 KB Output is correct
33 Correct 161 ms 30072 KB Output is correct
34 Correct 28 ms 25600 KB Output is correct
35 Correct 59 ms 27588 KB Output is correct
36 Correct 88 ms 29816 KB Output is correct
37 Correct 140 ms 32120 KB Output is correct
38 Correct 205 ms 34424 KB Output is correct
39 Correct 285 ms 37240 KB Output is correct
40 Correct 385 ms 40568 KB Output is correct
41 Correct 389 ms 41080 KB Output is correct