Submission #934039

#	Time	Username	Problem	Language	Result	Execution time	Memory
934039		vjudge1	Bridges (APIO19_bridges)	C++17	43 / 100	3055 ms	20084 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);
    }
};

struct Query { char type; ll a, b, i; };
struct Edge { ll u, v, w; };
vector <Edge> egs;

struct DSU {
    vll par;
    vll sz;
    ll n;
    
    DSU (ll n): par(n), sz(n, 1) {
        iota(par.begin(), par.end(), 0);
    }

    ll find (ll u) {
        return (u == par[u] ? u : par[u] = find(par[u]));
    }

    void join (ll u, ll v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (sz[u] > sz[v]) swap(u, v);
        par[u] = v;
        sz[v] += sz[u];
    }

    ll findSize (ll u) {
        return sz[find(u)];
    }
};

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);
        egs.push_back({ u, v, 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;
        vector <Query> qs(Q);
        for (ll i = 0; i < Q; i++) qs[i].i = i;
        for (auto &[type, a, b, i] : qs) cin >> type >> a >> b;
        bool only2=true;
        for (auto [type, a, b, i] : qs) only2 &= type=='2';
        // cerr << (only2 ? "NOLY 2" : "ALOS 1") << '\n';
        if (only2) {
            sort(egs.begin(), egs.end(), [&](const Edge &a, const Edge &b) {
                return a.w > b.w;
            });
            sort(qs.begin(), qs.end(), [&](const Query &a, const Query &b) {
                return a.b > b.b;
            });
            ll p1=0;
            vll vans(Q, -16);
            DSU dsu(n);
            for (ll p2 = 0; p2 < Q; p2++) {
                while (p1 < egs.size() && egs[p1].w >= qs[p2].b) {
                    dsu.join(egs[p1].u, egs[p1].v);
                    p1++;
                }
                vans[qs[p2].i] = dsu.findSize(qs[p2].a-1);
            }
            for (ll i : vans) cout << i << '\n';
        } else {
            for (auto [type, a, b, i] : qs) {
                switch (type) {
                    case '1':
                    {ll i, w;
                    i=a, w=b;
                    i--;
                    wei[i] = w;}
                    break;
                    case '2':
                    {ll u, w;
                    u=a, w=b;
                    u--;
                    timer++;
                    cout << dfs(u, w) << '\n';}
                    break;
                }
            }
        }
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:180:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |                 while (p1 < egs.size() && egs[p1].w >= qs[p2].b) {
      |                        ~~~^~~~~~~~~~~~

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