Submission #936423

#	Time	Username	Problem	Language	Result	Execution time	Memory
936423		sleepntsheep	Bridges (APIO19_bridges)	C++17	100 / 100	2277 ms	5324 KiB

bridges

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,tune=native")
#define INLINE inline __attribute__((always_inline))

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 600
int n,m,e[100000][3],h[N],q,b[100000][3],delta[100000],stat[100000],rm,rizz[9000],sm,ask[9000],am;

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

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

INLINE 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 compar_edge_dec2(int i,int j){return e[i][2]>e[j][2];}
int compar_ask_dec2(int i,int j){return b[i][2]>b[j][2];}

#include<algorithm>
int onrizz[100000],ans[100000];
int main()
{
    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)
    {
        memset(p,-1,sizeof p);svtop=0;
        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;
        std::sort(stat,stat+sm,compar_edge_dec2); std::sort(ask,ask+am,compar_ask_dec2);
        int ep=0;
        for(int ii=0;ii<am;++ii)
        {
            int w=b[ask[ii]][2];
            savemode=0;while(ep<sm&&e[stat[ep]][2]>=w)dun(e[stat[ep]][0],e[stat[ep]][1]),++ep;savemode=1;
            int eee=svtop;
            for(int j=ask[ii]-1;j>=l*S;--j)
            {
                if(b[j][0]==1&&!onrizz[b[j][1]])
                {
                    if(b[j][2]>=w)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]]&&e[rizz[jj]][2]>=w)
                dun(e[rizz[jj]][0],e[rizz[jj]][1]);
            ans[ask[ii]]=-p[df(b[ask[ii]][1])];
            while(svtop>eee)drb();
            for(int j=ask[ii]-1;j>=l*S;--j) onrizz[b[j][1]]=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]],e[b[j][1]][2]=b[j][2];
    }
    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:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:47:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     for(int i=0;i<m;++i)scanf("%d%d%d",e[i],e[i]+1,e[i]+2);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
bridges.cpp:49:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     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: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27