Submission #196905

#	Time	Username	Problem	Language	Result	Execution time	Memory
196905		Andrei_Cotor	Bridges (APIO19_bridges)	C++14	100 / 100	2820 ms	9644 KiB

bridges

#include<iostream>
#include<algorithm>
#define BUCK 700

using namespace std;

typedef struct edge
{
    int x,y,c;
} EDGE;

typedef struct qry
{
    int t,x,y,ind;
} QRY;

bool cmp(EDGE a, EDGE b)
{
    return a.c>b.c;
}

bool cmp2(QRY a, QRY b)
{
    return a.y>b.y;
}

EDGE Edges[100005],EdgeLeft[100005];
QRY Q[100005],Updates[BUCK+5],Queries[BUCK+5];
int Sz[50005],P[50005],top,Rez[100005];
bool Updated[100005],Viz[100005];
pair<int,int> S[BUCK+5];

int parent(int x)
{
    while(P[x]!=0)
        x=P[x];
    return x;
}

void unite(int x, int y, bool reversable)
{
    x=parent(x);
    y=parent(y);

    if(x==y)
        return;

    if(Sz[x]>Sz[y])
    {
        if(reversable)
            S[++top]={y,x};

        Sz[x]+=Sz[y];
        P[y]=x;
    }
    else
    {
        if(reversable)
            S[++top]={x,y};

        Sz[y]+=Sz[x];
        P[x]=y;
    }
}

void revDSU()
{
    while(top)
    {
        P[S[top].first]=0;
        Sz[S[top].second]-=Sz[S[top].first];
        top--;
    }
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

    int n,m;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
        cin>>Edges[i].x>>Edges[i].y>>Edges[i].c;

    int q;
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        cin>>Q[i].t>>Q[i].x>>Q[i].y;
        Q[i].ind=i;
    }

    for(int st=1, dr=BUCK; st<=q; st+=BUCK, dr+=BUCK)
    {
        dr=min(dr,q);

        for(int i=1; i<=m; i++)
            Viz[i]=0;

        for(int i=1; i<=n; i++)
        {
            Sz[i]=1;
            P[i]=0;
        }

        int nru=0,nrq=0;
        for(int i=st; i<=dr; i++)
        {
            if(Q[i].t==1)
            {
                Updates[++nru]=Q[i];
                Viz[Q[i].x]=1;
            }
            else
                Queries[++nrq]=Q[i];
        }

        int nrel=0;
        for(int i=1; i<=m; i++)
        {
            if(!Viz[i])
                EdgeLeft[++nrel]=Edges[i];
        }

        sort(EdgeLeft+1,EdgeLeft+nrel+1,cmp);
        sort(Queries+1,Queries+nrq+1,cmp2);

        int ie=1;
        for(int iq=1; iq<=nrq; iq++)
        {
            while(ie<=nrel && Queries[iq].y<=EdgeLeft[ie].c)
            {
                unite(EdgeLeft[ie].x,EdgeLeft[ie].y,0);
                ie++;
            }

            for(int i=1; i<=nru; i++)
                Updated[Updates[i].x]=0;

            int start=1;
            while(start<=nru && Updates[start].ind<Queries[iq].ind)
                start++;

            for(int iu=start-1; iu>=1; iu--)
            {
                if(Updated[Updates[iu].x])
                    continue;

                Updated[Updates[iu].x]=1;
                if(Updates[iu].y>=Queries[iq].y)
                    unite(Edges[Updates[iu].x].x,Edges[Updates[iu].x].y,1);
            }

            for(int iu=start; iu<=nru; iu++)
            {
                if(Updated[Updates[iu].x])
                    continue;

                if(Edges[Updates[iu].x].c>=Queries[iq].y)
                    unite(Edges[Updates[iu].x].x,Edges[Updates[iu].x].y,1);
            }

            Rez[Queries[iq].ind]=Sz[parent(Queries[iq].x)];

            revDSU();
        }

        for(int i=1; i<=nru; i++)
            Edges[Updates[i].x].c=Updates[i].y;
    }

    for(int i=1; i<=q; i++)
    {
        if(Q[i].t==2)
            cout<<Rez[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