Submission #568743

#	Time	Username	Problem	Language	Result	Execution time	Memory
568743		shrimb	Bridges (APIO19_bridges)	C++17	13 / 100	82 ms	10396 KiB

bridges

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 100001;
const int N = exp2(ceil(log2(maxn)));

vector<pair<int,int>> adj[maxn];
int w[maxn];

int dsu[maxn];
int sz[maxn];

int Find (int x) {
    return dsu[x] == x ? x : dsu[x] = Find(dsu[x]);
}

void Union (int a, int b) {
    int x = Find(a), y = Find(b);
    if (x==y) return;
    sz[y] += sz[x];
    dsu[x] = y;
}

int seg[2 * N];
int Left, Right, Pos, Val;

int Combine (int a, int b) {
    return min(a, b);
}

int Query (int l = 1, int r = N, int ind = 1) {
    if (l > Right || r < Left) return INT_MAX ;
    if (l >= Left and r <= Right) return seg[ind];
    int m = (l + r) / 2;
    return Combine(Query(l, m, ind * 2), Query(m + 1, r, ind * 2 + 1));
}

void Update () {
    int ind = N + Pos - 1;
    seg[ind] = Val;
    while (ind /= 2) seg[ind] = Combine(seg[ind * 2], seg[ind * 2 + 1]);
}

signed main () {
    cin.tie(0)->sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    bool LINE = m == n - 1;

    for (int i = 0 ; i < m ; i++) {
        int u, v, x;
        cin >> u >> v >> x;
        adj[u].emplace_back(v, i + 1);
        adj[v].emplace_back(u, i + 1);
        seg[N + i] = x;
        LINE &= (u == v + 1);
        w[i + 1] = x;
    }

    for (int i = N - 1 ; i ; i--) {
        seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
    }

    int q;
    cin >> q;
    if (n <= 1000 and m <= 1000 and q <= 10000) {
        while (q--) {
            int t;
            cin >> t;
            if (t == 1) {
                int b, r;
                cin >> b >> r;
                w[b] = r;
            } else {
                int s, wj;
                cin >> s >> wj;
                for (int i = 1 ; i <= n ; i++) dsu[i] = i, sz[i] = 1;
                for (int i = 1 ; i <= n ; i++) for (auto [j, b] : adj[i]) if (w[b] >= wj) Union(i, j);
                cout << sz[Find(s)] << endl;
            }
        }
        return 0;
    }

    if (LINE) {
        while (q--) {
            int t;
            cin >> t;
            if (t == 1) {
                cin >> Pos >> Val;
                Update();
            } else {
                int i, wj;
                cin >> i >> wj;
                // {i...m}
                // {1...i-1}
                int left, right;
                {
                    int l = i, r = m + 1;
                    while (r - l > 1) {
                        int m = (l + r) / 2;
                        Left=  i, Right = m;
                        if (Query() >= wj) l = m;
                        else r = m;
                    }
                    right = l;
                }
                {
                    int l = 0, r = i - 1;
                    while (r - l > 1) {
                        int m = (l + r) / 2;
                        Left = m, Right = i-1;
                        if (Query() >= wj) r = m;
                        else l = m;
                    }
                    left = r;
                }
                cout << right - left + 2 << endl;
            }
        }
    }
}

Compilation message (stderr)

bridges.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | //\
      | ^

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