Submission #886307

#	Time	Username	Problem	Language	Result	Execution time	Memory
886307		andrei_boaca	Bridges (APIO19_bridges)	C++17	13 / 100	4413 ms	524288 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
const int bucksize=320;
int n,m,q;
pii g[100005];
int b[100005];
int last[100005];
int sol[100005];
int par[321][50005],sz[321][50005];
struct date
{
    int tip;
    int l,r,val;
    int ind;
};
vector<date> ev;
vector<int> add[100005];
int getbuck(int x)
{
    return x/bucksize+(x%bucksize!=0);
}
bool evcomp(date a, date b)
{
    if(a.val!=b.val)
        return a.val>b.val;
    return a.tip<b.tip;
}
int nrpasi=0;
int getpar(int buck,int nod)
{
    nrpasi++;
    if(par[buck][nod]==nod)
        return nod;
    return getpar(buck,par[buck][nod]);
}
void plsput(int l,int r,int ind)
{
    int b1=getbuck(l);
    int b2=getbuck(r);
    if(b1==b2)
    {
        for(int i=l;i<=r;i++)
            add[i].push_back(ind);
        return;
    }
    for(int i=b1+1;i<b2;i++)
    {
        nrpasi=0;
        int a=getpar(i,g[ind].first);
        assert(nrpasi<=20);
        nrpasi=0;
        int b=getpar(i,g[ind].second);
        assert(nrpasi<=20);
        if(a!=b)
        {
            if(sz[a]<sz[b])
                swap(a,b);
            par[i][b]=a;
            sz[i][a]+=sz[i][b];
        }
    }
    for(int i=l;getbuck(i)==b1&&i<=r;i++)
        add[i].push_back(ind);
    for(int i=r;getbuck(i)==b2&&i>=l;i--)
        add[i].push_back(ind);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>g[i].first>>g[i].second>>b[i];
        last[i]=0;
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int tip;
        cin>>tip;
        if(tip==2)
        {
            int nod,val;
            cin>>nod>>val;
            ev.push_back({2,i,i,val,nod});
        }
        else
        {
            int ind,val;
            cin>>ind>>val;
            int st=last[ind]+1;
            int dr=i;
            if(st<=dr)
                ev.push_back({1,st,dr,b[ind],ind});
            last[ind]=i;
            b[ind]=val;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int st=last[i]+1;
        int dr=q;
        if(st<=dr)
            ev.push_back({1,st,dr,b[i],i});
    }
    sort(ev.begin(),ev.end(),evcomp);
    int bks=getbuck(q);
    for(int i=1;i<=bks;i++)
        for(int j=1;j<=n;j++)
        {
            par[i][j]=j;
            sz[i][j]=1;
        }
    for(date z:ev)
    {
        int tip=z.tip;
        if(tip==1)
        {
            int l=z.l,r=z.r;
            int ind=z.ind;
            plsput(l,r,ind);
        }
        else
        {
            int nod=z.ind;
            int timp=z.l;
            stack<pii> stiva;
            int buck=getbuck(timp);
            for(int i:add[timp])
            {
                int a=getpar(buck,g[i].first);
                int b=getpar(buck,g[i].second);
                if(a!=b)
                {
                    if(sz[a]<sz[b])
                        swap(a,b);
                    par[buck][b]=a;
                    sz[buck][a]+=sz[buck][b];
                    stiva.push({a,b});
                }
            }
            sol[timp]=sz[buck][getpar(buck,nod)];
            while(!stiva.empty())
            {
                int a=stiva.top().first;
                int b=stiva.top().second;
                stiva.pop();
                sz[buck][a]-=sz[buck][b];
                par[buck][b]=b;
            }
        }
    }
    for(int i=1;i<=q;i++)
        if(sol[i]!=0)
            cout<<sol[i]<<'\n';
    return 0;
}

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