제출 #934031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934031		vjudge1	다리 (APIO19_bridges)	C++17	29 / 100	3046 ms	12492 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll IDEM = 1E18+16;
const ll MAXN = 5E4+16;
vector <pair <ll, ll> > adj[MAXN];
vll wei;
ll vis[MAXN];
ll timer=0;

ll dfs (ll u, ll w) {
    if (vis[u]==timer) return 0;
    vis[u]=timer;
    ll ans=1;
    for (auto [v, i] : adj[u]) {
        if (wei[i] < w) continue;
        ans += dfs(v, w);
    }
    return ans;
}

#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
    vll tree;
    ll n;

    SegTree (ll n): tree(2*n, IDEM), n(n) {}

    void pull (ll l, ll r, ll id) {
        tree[id] = min(tree[id+1], tree[id+off]);
    }

    void update (ll at, ll val, ll l, ll r, ll id) {
        if (at < l || r < at) return;
        if (at <= l && r <= at) {
            tree[id]=val;
            return;
        }
        update(at, val, l, mid, id+1);
        update(at, val, mid+1, r, id+off);
        pull(l, r, id);
    }

    void update (ll at, ll val) {
        update(at, val, 0, n-1, 0);
    }

    ll query (ll ql, ll qr, ll l, ll r, ll id) {
        if (qr < l || r < ql) return IDEM;
        if (ql <= l && r <= qr) return tree[id];
        return min(query(ql, qr, l, mid, id+1), query(ql, qr, mid+1, r, id+off));
    }

    ll query (ll ql, ll qr) {
        return query(ql, qr, 0, n-1, 0);
    }
};

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    SegTree st(m);
    bool isL = (n-1==m);
    for (ll i = 0; i < m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        isL &= (u==i && v==i+1);
        adj[u].push_back({ v, i });
        adj[v].push_back({ u, i });
        wei.push_back(w);
        st.update(i, w);
    }
    // cerr << (isL ?" IS LINE ": "NO LINE") << '\n';
    if (isL) {
    ll Q;
    cin >> Q;
    while (Q--) {
        char type;
        cin >> type;
        switch (type) {
            case '1':
            {ll i, w;
            cin >> i >> w;
            i--;
            st.update(i, w);}
            break;
            case '2':
            {ll u, w;
            cin >> u >> w;
            u--;
            ll ans=1;
            if (u>0 && st.query(u-1, u-1) >= w) { // to the left
                ll l=-1, r=u-1;
                while (l+1 < r) {
                    ll midBS = (l+r)>>1;
                    ll ww = st.query(midBS, r);
                    if (ww < w) {
                        l = midBS;
                    } else {
                        r = midBS;
                    }
                }
                ans += u-r;
            }
            if (u<m && st.query(u, u) >= w) {
                ll l=u, r=m;
                while (l+1 < r) {
                    ll midBS = (l+r)>>1;
                    ll ww = st.query(l, midBS);
                    if (ww < w) {
                        r = midBS;
                    } else {
                        l = midBS;
                    }
                }
                ans += l-u+1;
            }
            cout << ans << '\n';
            }
            break;
        }
    }
    } else {
        ll Q;
    cin >> Q;
    while (Q--) {
        char type;
        cin >> type;
        switch (type) {
            case '1':
            {ll i, w;
            cin >> i >> w;
            i--;
            wei[i] = w;}
            break;
            case '2':
            {ll u, w;
            cin >> u >> w;
            u--;
            timer++;
            cout << dfs(u, w) << '\n';}
            break;
        }
    }
    }
    return 0;
}

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