Submission #987803

#	Time	Username	Problem	Language	Result	Execution time	Memory
987803		876pol	Bridges (APIO19_bridges)	C++17	29 / 100	3028 ms	16760 KiB

bridges

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using int128 = __int128_t;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define TRAV(e, a) for (const auto &e : a)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
    out << "[";
    for (auto it = obj.begin(); it != obj.end(); it++) {
        out << &", "[2 * (it == obj.begin())] << *it;
    }
    return out << "]";
}

template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
    return out << "(" << obj.first << ", " << obj.second << ")";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    bool st2 = true;
    ll n, m;
    cin >> n >> m;
    st2 &= (m == n - 1);
    vec<vec<pll>> graph(n + 1);
    vec<ll> w(m + 1);
    CFOR(i, 1, m) {
        ll a, b;
        cin >> a >> b >> w[i];
        graph[a].push_back({b, i});
        graph[b].push_back({a, i});
        st2 &= (a + 1 == b);
    }
    ll q;
    cin >> q;
    vec<vec<ll>> queries(q, vec<ll>(3));
    FOR(i, 0, q) {
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
    }

    if (st2) {
        const ll SZ = 3;
        vec<ll> b(n / SZ + 1, 1e9);
        CFOR(i, 0, n - 1) b[i / SZ] = min(b[i / SZ], w[i]);
        FOR(i, 0, q) {
            if (queries[i][0] == 1) {
                ll bind = queries[i][1] / SZ;
                w[queries[i][1]] = queries[i][2];
                b[bind] = 1e9;
                FOR(i, bind * SZ, min((bind + 1) * SZ, n)) {
                    b[bind] = min(b[bind], w[i]);
                }
            } else {
                ll bind = queries[i][1] / SZ;
                if (queries[i][2] > b[bind]) {
                    ll l = queries[i][1], r = queries[i][1];
                    while (1 < l && w[l - 1] >= queries[i][2]) l--;
                    while (r < n && w[r] >= queries[i][2]) r++;
                    cout << r - l + 1 << "\n";
                } else {
                    ll bl = bind, br = bind;
                    while (0 < bl && b[bl - 1] >= queries[i][2]) bl--;
                    while (br < b.size() && b[br] >= queries[i][2]) br++;
                    ll l = bl * SZ;
                    ll r = min(br * SZ, n);
                    while (1 < l && w[l - 1] >= queries[i][2]) l--;
                    while (r < n && w[r] >= queries[i][2]) r++;
                    cout << r - l + 1 << "\n";
                }
            }
        }

    } else {
        vec<bool> visited(n + 1);
        FOR(i, 0, q) {
            if (queries[i][0] == 1) {
                w[queries[i][1]] = queries[i][2];
            } else {
                fill(all(visited), 0ll);
                function<void(ll)> dfs = [&](ll curr) {
                    visited[curr] = 1;
                    TRAV(e, graph[curr]) {
                        if (visited[e.first] || queries[i][2] > w[e.second])
                            continue;
                        dfs(e.first);
                    }
                };
                dfs(queries[i][1]);
                cout << accumulate(all(visited), 0ll) << "\n";
            }
        }
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:84:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int, std::allocator<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                     while (br < b.size() && b[br] >= queries[i][2]) br++;
      |                            ~~~^~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27