Submission #936392

#	Time	Username	Problem	Language	Result	Execution time	Memory
936392		sleepntsheep	Bridges (APIO19_bridges)	C++17	0 / 100	1988 ms	10076 KiB

bridges

#include<stdio.h>
#include<string.h>

unsigned X=12345;int rand_(){return(X*=3)/2;}
int(*compar)(int,int);
void sort(int*aa,int l,int r)
{
    while(l<r)
    {
        int i=l,j=l,k=r,t,p=aa[l+rand_()%(r-l)];
        while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:t=aa[i],aa[i]=aa[j],aa[j]=t,++i,++j;break;case 1:t=aa[--k],aa[k]=aa[j],aa[j]=t;break;}
        sort(aa,l,i),l=k;
    }
}

#define N 50005
#define S 3000
int n,m,e[N][3],h[N],q,b[100000][3],delta[100000],stat[100000],rm,rizz[9000],sm,ask[9000],am;

int p[N],sve[200000][3],svtop;
int df(int x){return p[x]<0?x:df(p[x]);}

int dun(int u,int v){
    if((u=df(u))==(v=df(v)))return 0;
    if(-p[u]<-p[v]){int t=u;u=v;v=t;}
    sve[svtop][0]=u,sve[svtop][1]=v,sve[svtop][2]=p[v],++svtop;
    p[u]+=p[v],p[v]=u;
    return 1;
}

void drb(){int k=--svtop,u=sve[k][0],v=sve[k][1],pv=sve[k][2];p[u]-=(p[v]=pv);}

int compar_edge_dec(int i,int j){return e[i][2]>e[j][2]?-1:e[i][2]<e[j][2]?1:0;}
int compar_ask_dec(int i,int j){return b[i][2]<b[j][2]?1:b[i][2]>b[j][2]?-1:0;}

int onrizz[100000],ans[100000];

int main()
{
    memset(p,-1,sizeof p);
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i)scanf("%d%d%d",e[i],e[i]+1,e[i]+2);
    scanf("%d",&q);
    for(int i=0;i<q;++i){scanf("%d%d%d",b[i],b[i]+1,b[i]+2);if(b[i][0]==1)--b[i][1];}
    for(int l=0;l*S<q;++l)
    {
        for(int j=l*S;j<l*S+S&&j<q;++j)if(b[j][0]==1)++delta[b[j][1]];else ask[am++]=j;
        for(int j=0;j<m;++j)if(!delta[j])stat[sm++]=j;else rizz[rm++]=j;
        compar=compar_edge_dec;sort(stat,0,sm);
        compar=compar_ask_dec;sort(ask,0,am);
        if(0)
        {
        puts("EDGE");
        for(int j=0;j<sm;++j)printf("%d %d %d\n",e[stat[j]][0],e[stat[j]][1],e[stat[j]][2]);
        puts("QUERY");
        for(int j=0;j<am;++j)printf("%d %d %d\n",b[ask[j]][0],b[ask[j]][1],b[ask[j]][2]);
        }
        int ep=0;
        for(int ii=0;ii<am;++ii)
        {
            int w=b[ask[ii]][2];
            while(ep<sm&&e[stat[ep]][2]>=w)dun(e[stat[ep]][0],e[stat[ep]][1]),++ep;
            //printf(" AT %d %d %d\n",ii,ep,w);
            int eee=0;
            for(int j=ask[ii]-1;j>=l*S;--j)
            {
                if(b[j][0]==1&&!onrizz[b[j][1]])
                {
                    if(b[j][2]>=w)
                    {
                        //printf("RIZZING %d %d %d\n",b[j][1],w,b[j][2]);
                        eee+=dun(e[b[j][1]][0],e[b[j][1]][1]);
                    }
                    onrizz[b[j][1]]=1;
                }
            }
            for(int jj=0;jj<rm;++jj)if(!onrizz[rizz[jj]])
            {

                if(e[rizz[jj]][2]>=w)
                {
                    //printf("RIZZING %d\n",rizz[jj]);
                    eee+=dun(e[rizz[jj]][0],e[rizz[jj]][1]);
                }
                onrizz[rizz[jj]]=1;
            }
            ans[ask[ii]]=-p[df(b[ask[ii]][1])];
            while(eee--)drb();
            for(int j=ask[ii]-1;j>=l*S;--j) onrizz[b[j][1]]=0;
            for(int jj=0;jj<rm;++jj)onrizz[rizz[jj]]=0;
        }

        sm=rm=am=0;
        for(int j=l*S;j<l*S+S&&j<q;++j)if(b[j][0]==1)--delta[b[j][1]];
    }
    for(int i=0;i<q;++i)if(b[i][0]==2)printf("%d\n",ans[i]);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:42:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     for(int i=0;i<m;++i)scanf("%d%d%d",e[i],e[i]+1,e[i]+2);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
bridges.cpp:44:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     for(int i=0;i<q;++i){scanf("%d%d%d",b[i],b[i]+1,b[i]+2);if(b[i][0]==1)--b[i][1];}
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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