Submission #292029

#	Time	Username	Problem	Language	Result	Execution time	Memory
292029		Diuven	Express 20/19 (ROI19_express)	C++17	100 / 100	1162 ms	265896 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;

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

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 / 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