Submission #900256

#	Time	Username	Problem	Language	Result	Execution time	Memory
900256		12345678	Bridges (APIO19_bridges)	C++17	100 / 100	1898 ms	14860 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int nx=5e4+5, mx=1e5+5, qx=1e5+5, kx=320;

struct edge
{
    int u, v, w;
    edge(): u(0), v(0), w(0){}
    edge(int u, int v, int w): u(u), v(v), w(v){}
    bool operator< (const edge &o) const
    {
        if(w!=o.w)return w>o.w;
        if(u!=o.u)return u<o.u;
        return v<o.v;
    }
} ed[mx];

struct query
{
    int t, s, w;
} qr[qx];

struct dsu
{
    int dsu[nx], sz[nx];
    stack<pair<int, int>> s;
    void init()
    {
        for (int i=1; i<nx; i++) dsu[i]=i, sz[i]=1;
        while (!s.empty()) s.pop();
    }
    int find(int u)
    {
        if (u==dsu[u]) return u;
        return find(dsu[u]);
    }
    int size(int u)
    {
        return sz[find(u)];
    }
    void merge(int u, int v)
    {
        int pu=find(u), pv=find(v);
        if (pu==pv) return;
        if (sz[pu]<sz[pv]) swap(pu, pv);
        sz[pu]+=sz[pv];
        dsu[pv]=pu;
        s.push({pu, pv});
    }
    void undo(int x)
    {
        while (s.size()>x)
        {
            auto [u, v]=s.top();
            s.pop();
            sz[u]-=sz[v];
            dsu[v]=v;
        }
    }
} d;

int n, m, q, res[qx], used[mx];
multiset<edge> ms;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>ed[i].u>>ed[i].v>>ed[i].w, ms.insert(ed[i]);
    cin>>q;
    for (int i=1; i<=q; i++) cin>>qr[i].t>>qr[i].s>>qr[i].w;
    for (int l=1, r=kx; l<=q; l+=kx, r+=kx)
    {
        r=min(r, q);
        d.init();
        vector<int> upd;
        for (int i=l; i<=r; i++)
        {
            int id=qr[i].s;
            if (qr[i].t==1&&!used[id])
            {
                used[id]=1;
                upd.push_back(id);
                ms.erase(ms.find(ed[id]));
            }
        }
        vector<tuple<int, int, vector<int>>> c;
        for (int i=l; i<=r; i++)
        {
            if (qr[i].t==1) ed[qr[i].s].w=qr[i].w;
            else
            {
                vector<int> tmp;
                for (auto vl:upd) if (ed[vl].w>=qr[i].w) tmp.push_back(vl);
                c.push_back(make_tuple(qr[i].w, i, tmp));
            }
        }
        sort(c.begin(), c.end());
        reverse(c.begin(), c.end());
        //for (auto x:ms) cout<<"multiset "<<x.u<<' '<<x.v<<' '<<x.w<<'\n';
        auto itr=ms.begin();
        for (auto [cw, idx, up]:c)
        {
            while (itr!=ms.end()&&itr->w>=cw) d.merge(itr->u, itr->v), itr++;
            int st=d.s.size();
            for (auto tmp:up) d.merge(ed[tmp].u, ed[tmp].v);
            //if (idx==8) cout<<qr[idx].s<<' '<<d.find(qr[idx].s)<<' '<<d.sz[d.find(qr[idx].s)]<<'\n';
            res[idx]=d.size(qr[idx].s);
            d.undo(st);
        }
        for (auto x:upd) used[x]=0, ms.insert(ed[x]);
    }
    for (int i=1; i<=q; i++) if (qr[i].t==2) cout<<res[i]<<'\n';
}

Compilation message (stderr)

bridges.cpp: In member function 'void dsu::undo(int)':
bridges.cpp:54:24: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         while (s.size()>x)
      |                ~~~~~~~~^~

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