Submission #713632

#	Time	Username	Problem	Language	Result	Execution time	Memory
713632		bin9638	Bridges (APIO19_bridges)	C++17	100 / 100	1552 ms	10896 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 100010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double

struct canh
{
    int u,v,L,id;

    bool operator<(const canh&A)const
    {
        return L>A.L;
    }
}edge[N],g[N];

struct truyvan
{
    int type,id,val,cs;

    bool operator<(const truyvan&A)const
    {
        return val>A.val;
    }
}tv[N];
vector<truyvan>s;

struct DSU
{
    int lab[N]={},dem=0;

    void init()
    {
        memset(lab,-1,sizeof(lab));
        dem=0;
    }

    struct roll
    {
        int u,v,val_u,val_v;
    }luu[N];

    int root_roll_back(int u)
    {
        if(lab[u]<0)
            return u;
        return root_roll_back(lab[u]);
    }

    void update_roll_back(int u,int v)
    {
        if((u=root_roll_back(u))==(v=root_roll_back(v)))
            return;
        if(lab[u]>lab[v])
            swap(u,v);
        luu[++dem]={u,v,lab[u],lab[v]};
        lab[u]+=lab[v];
        lab[v]=u;
    }

    void roll_back()
    {
        for(int i=dem;i>=1;i--)
        {
            lab[luu[i].u]=luu[i].val_u;
            lab[luu[i].v]=luu[i].val_v;
        }
        dem=0;
    }

    int root(int u)
    {
        if(lab[u]<0)
            return u;
        return(lab[u]=root(lab[u]));
    }

    void update(int u,int v)
    {
        if((u=root(u))==(v=root(v)))
            return;
        if(lab[u]>lab[v])
            swap(u,v);
        lab[u]+=lab[v];
        lab[v]=u;
    }
}T;

int kq[N],n,m,q,ktr[N],times,chon[N];
vector<int>lis;

void solve(int l,int r)
{
    for(int i=1;i<=m;i++)
        g[i]=edge[i];
    sort(g+1,g+1+m);
    T.init();
    lis.clear();
    memset(ktr,0,sizeof(ktr));
    for(int i=l;i<=r;i++)
        if(tv[i].type==1)
            ktr[tv[i].id]=i,lis.pb(tv[i].id);
    s.clear();
    for(int i=l;i<=r;i++)
        if(tv[i].type==2)
            s.pb(tv[i]);
    sort(s.begin(),s.end());
    int pos=1;
    for(auto cc:s)
    {
        int u=cc.id,val=cc.val;
        while(pos<=m&&g[pos].L>=val)
        {
            if(ktr[g[pos].id]==0)
                T.update(g[pos].u,g[pos].v);
            pos++;
        }
        times++;
        for(int i=cc.cs;i>=l;i--)
            if(tv[i].type==1&&chon[tv[i].id]!=times)
            {
                chon[tv[i].id]=times;
                if(tv[i].val>=val)
                    T.update_roll_back(edge[tv[i].id].u,edge[tv[i].id].v);
            }
        for(auto k:lis)
            if(chon[k]!=times)
            {
                //cout<<k<<" "<<tv[k].val<<endl;
                chon[k]=times;
                if(edge[k].L>=val)
                    T.update_roll_back(edge[k].u,edge[k].v);
            }
        kq[cc.cs]=-T.lab[T.root_roll_back(u)];
        T.roll_back();
    }
}

int main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i].u>>edge[i].v>>edge[i].L;
        edge[i].id=i;
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>tv[i].type>>tv[i].id>>tv[i].val;
        tv[i].cs=i;
    }
    for(int pos=1;pos<=q;pos+=1000)
    {
        solve(pos,pos+1000-1);
        for(int i=pos;i<pos+1000;i++)
            if(tv[i].type==1)
                edge[tv[i].id].L=tv[i].val;
    }
    for(int i=1;i<=q;i++)if(kq[i]!=0)cout<<kq[i]<<"\n";
    return 0;
}

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