Submission #648766

#	Time	Username	Problem	Language	Result	Execution time	Memory
648766		ToroTN	Bridges (APIO19_bridges)	C++14	0 / 100	3067 ms	5536 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
int n,m,num=sqrt(100000),u[50005],v[50005],w[50005],ans[100005];
int op[100005],a[100005],b[100005],t,group[50005],mx=-1,mxmum,len[50005];
int p[50005],sz[50005],it1,it2,edge,memp[50005],memsz[50005],hsh[100005];
int latest[50005],uay[50005],taq[50005];
vector<tuple<int,int,int> > g,reset;
vector<tuple<int,int,int,int> > query;
int f(int a)
{
    if(p[a]==a)return a;
    return p[a]=f(p[a]);
}
void un(int b,int c)
{
    if(f(b)!=f(c))
    {
        sz[f(c)]+=sz[f(b)];
        p[f(b)]=f(c);
    }
}
void chk()
{
    for(int i=1;i<=n;i++)
    {
        printf("%d ",p[i]);
    }
    printf("\n");
    for(int i=1;i<=n;i++)
    {
        printf("%d ",sz[i]);
    }
    printf("\n\n");
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
        g.pb({w[i],i,0});
        group[i]=(i-1)/num+1;
        mx=max(mx,group[i]);
    }
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d%d",&op[i],&a[i],&b[i]);
        if(op[i]==1)g.pb({b[i],a[i],i});
    }
    sort(g.begin(),g.end());
    for(int i=1;i<=mx;i++)
    {
        //printf("%d\n",i);
        for(int j=1;j<=n;j++)p[j]=j,sz[j]=1;
        for(int j=1;j<=m;j++)hsh[j]=0;
        for(int j=1;j<=m;j++)len[j]=w[j];
        for(int j=1;j<=num*(i-1);j++)len[j]=b[j];
        for(int j=num*(i-1)+1;j<=min(num*i,t);j++)
        {
            query.pb({b[j],a[j],op[j],j});
        }
        sort(query.begin(),query.end());
        /*printf("g\n");
        for(int j=g.size()-1;j>=0;j--)
        {
            printf("%d %d %d\n",get<0>(g[j]),get<1>(g[j]),get<2>(g[j]));
        }
        printf("query\n");
        for(int j=query.size()-1;j>=0;j--)
        {
            printf("%d %d %d %d\n",get<0>(query[j]),get<1>(query[j]),get<2>(query[j]),get<3>(query[j]));
        }
        printf("\n");*/
        it1=g.size()-1;
        it2=query.size()-1;
        for(int j=0;j<query.size();j++)
        {
            if(get<2>(query[j])==1)
            {
                edge=get<1>(query[j]);
                ++hsh[edge];
            }
        }
        mxmum=1e9;
        while(it2>=0)
        {
            if(get<2>(query[it2])==1)
            {
                --it2;
                continue;
            }
            if(it1>=0)
            {
                if(get<0>(g[it1])>=get<0>(query[it2]))
                {
                    if(get<2>(g[it1])<=num*(i-1)&&hsh[get<1>(g[it1])]==0)
                    {
                        un(u[get<1>(g[it1])],v[get<1>(g[it1])]);
                    }
                    mxmum=get<0>(g[it1]);
                    --it1;
                    continue;
                }
            }
            //printf("%d %d\n",it1,it2);
            //printf("answer the question no.%d\n",get<3>(query[it2]));
            reset.clear();
            //chk();
            for(int j=0;j<query.size();j++)
            {
                if(get<2>(query[j])==1)
                {
                    edge=get<1>(query[j]);
                    uay[edge]=0;
                }
            }
            for(int j=0;j<query.size();j++)
            {
                if(get<3>(query[j])<get<3>(query[it2])&&get<2>(query[j])==1)
                {
                    edge=get<1>(query[j]);
                    if(get<3>(query[j])>uay[edge])
                    {
                        uay[edge]=get<3>(query[j]);
                        latest[edge]=get<0>(query[j]);
                    }
                }else if(get<2>(query[j])==1)
                {
                    edge=get<1>(query[j]);
                    if(len[edge]>=mxmum)
                    {
                        taq[u[edge]]=0;
                        taq[v[edge]]=0;
                        reset.pb({u[edge],p[u[edge]],sz[u[edge]]});
                        reset.pb({v[edge],p[v[edge]],sz[v[edge]]});
                        taq[f(u[edge])]=0;
                        taq[f(v[edge])]=0;
                        reset.pb({f(u[edge]),p[f(u[edge])],sz[f(u[edge])]});
                        reset.pb({f(v[edge]),p[f(v[edge])],sz[f(v[edge])]});
                        un(u[edge],v[edge]);
                    }
                }
            }
            for(int j=0;j<query.size();j++)
            {
                if(get<3>(query[j])<get<3>(query[it2])&&get<2>(query[j])==1)
                {
                    edge=get<1>(query[j]);
                    if(latest[edge]>=mxmum)
                    {
                        taq[u[edge]]=0;
                        taq[v[edge]]=0;
                        reset.pb({u[edge],p[u[edge]],sz[u[edge]]});
                        reset.pb({v[edge],p[v[edge]],sz[v[edge]]});
                        taq[f(u[edge])]=0;
                        taq[f(v[edge])]=0;
                        reset.pb({f(u[edge]),p[f(u[edge])],sz[f(u[edge])]});
                        reset.pb({f(v[edge]),p[f(v[edge])],sz[f(v[edge])]});
                        un(u[edge],v[edge]);
                    }
                }
            }
            //chk();
            //printf("tee=%d\n",get<1>(query[it2]));
            reset.pb({get<1>(query[it2]),p[get<1>(query[it2])],sz[get<1>(query[it2])]});
            reset.pb({f(get<1>(query[it2])),p[f(get<1>(query[it2]))],sz[f(get<1>(query[it2]))]});
            taq[get<1>(query[it2])]=0;
            taq[f(get<1>(query[it2]))]=0;
            ans[get<3>(query[it2])]=sz[f(get<1>(query[it2]))];
            for(int j=0;j<reset.size();j++)
            {
                //printf("reset=%d %d %d\n",get<0>(reset[j]),get<1>(reset[j]),get<2>(reset[j]));
                if(taq[get<0>(reset[j])]==0)
                {
                    ++taq[get<0>(reset[j])];
                    p[get<0>(reset[j])]=get<1>(reset[j]);
                    sz[get<0>(reset[j])]=get<2>(reset[j]);
                }
            }
            //chk();
            --it2;
        }
    }
    for(int i=1;i<=t;i++)
    {
        if(op[i]==2)printf("%lld\n",ans[i]);
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int j=0;j<query.size();j++)
      |                     ~^~~~~~~~~~~~~
bridges.cpp:113:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for(int j=0;j<query.size();j++)
      |                         ~^~~~~~~~~~~~~
bridges.cpp:121:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             for(int j=0;j<query.size();j++)
      |                         ~^~~~~~~~~~~~~
bridges.cpp:148:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |             for(int j=0;j<query.size();j++)
      |                         ~^~~~~~~~~~~~~
bridges.cpp:174:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |             for(int j=0;j<reset.size();j++)
      |                         ~^~~~~~~~~~~~~
bridges.cpp:190:32: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  190 |         if(op[i]==2)printf("%lld\n",ans[i]);
      |                             ~~~^    ~~~~~~
      |                                |         |
      |                                |         int
      |                                long long int
      |                             %d
bridges.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d%d%d",&u[i],&v[i],&w[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d",&t);
      |     ~~~~~^~~~~~~~~
bridges.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d%d%d",&op[i],&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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