Submission #716519

#	Time	Username	Problem	Language	Result	Execution time	Memory
716519		1zaid1	Bridges (APIO19_bridges)	C++17	16 / 100	914 ms	115868 KiB

bridges

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

#define int long long
#define endl '\n'

const int M = 3e6+5, MOD = 998244353;
vector<int> node[M], tmp;
int vis[M], ind[M];

void dfs(int s) {
    vis[s] = true;
    for (auto i:node[s]) {
        if (!vis[i]) dfs(i);
    } tmp.push_back(s);
}

int N = 1 << 20;
int seg[M];

void update(int ind) {
    while (ind /= 2) seg[ind] = min(seg[ind*2], seg[ind*2+1]);
}

int query(int L, int R, int l = 1, int r = N, int ind = 1) {
    if (r < L || l > R) return INT_MAX;
    if (L <= l && r <= R) return seg[ind];
    return min(query(L, R, l, (l+r)/2, ind*2), query(L, R, (l+r)/2+1, r, ind*2+1));
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    for (int &i:seg) i = INT_MAX;

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

    vector<array<int, 3>> E;
    map<pair<int, int>, int> e;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        node[a].push_back(b);
        node[b].push_back(a);
        E.push_back({a, b, c});
        e[{a, b}] = e[{b, a}] = c;
    }

    int f = 0;
    for (int i = 1; i <= n; i++) if (node[i].size() == 1) f = i;
    dfs(f);
    
    for (int i = 0; i < n-1; i++) {
        seg[i+N] = e[{tmp[i], tmp[i+1]}];
        update(i+N);
    }

    for (int i = 0; i < n; i++) ind[tmp[i]] = i;
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x;

        if (x == 1) {
            cin >> x >> y;
            auto [a, b, c] = E[x-1];
            seg[min(ind[a], ind[b])+N] = y;
            update(min(ind[a], ind[b]) + N);
        } else {
            cin >> x >> y;

            int ans = 1;
            if (ind[x] != n-1) {
                int l = -1, p = (1<<20);
                while (p /= 2) {
                    if (ind[x]+l+p+1 >= n) continue;
                    if (query(ind[x]+1, ind[x]+l+p+1) >= y) l += p;
                } ans += l+1;
            }

            if (ind[x]) {
                int l = 0, p = (1<<20);
                while (p /= 2) {
                    if (ind[x]-(l+p) < 0) continue;
                    if (query(ind[x]-(l+p)+1, ind[x]) >= y) l += p;
                } ans += l;
            }

            cout << ans << endl;
        }
    }

    return 0;
}
/*
5 4
1 3 1
3 5 2
5 4 3
4 2 1
-1
2 2 2

*/

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