Submission #292030

#	Time	Username	Problem	Language	Result	Execution time	Memory
292030		Diuven	Express 20/19 (ROI19_express)	C++17	100 / 100	608 ms	265976 KiB

express

#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 (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 24 / 24
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11