Submission #222851

#	Time	Username	Problem	Language	Result	Execution time	Memory
222851		MKopchev	Bridges (APIO19_bridges)	C++14	100 / 100	2922 ms	9592 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;

int n,m;

struct edge
{
    int u,v,d;
};

edge inp[nmax];

int q;

struct quer
{
    int type,u,w;
};
quer queries[nmax];

int output[nmax];

int parent[nmax],SZ[nmax];

int root(int node)
{
    while(node!=parent[node])node=parent[node];
    return node;
}

pair<int/*big*/,int/*small*/> done[nmax];
int pointer=0;

void my_merge(int u,int v)
{
    u=root(u);
    v=root(v);

    if(u==v)return;

    if(SZ[u]<SZ[v])swap(u,v);

    parent[v]=u;
    SZ[u]+=SZ[v];

    pointer++;

    done[pointer]={u,v};
}

void my_pop()
{
    parent[done[pointer].second]=done[pointer].second;
    SZ[done[pointer].first]=SZ[done[pointer].first]-SZ[done[pointer].second];
    pointer--;
}

edge not_changed[nmax];
int pointer_not_changed=0;

int changed[nmax],pointer_changed=0;
int additional[nmax];

quer active_queries[nmax];
int pointer_queries=0;

bool keep[nmax];

bool cmp(edge a,edge b)
{
    return a.d<b.d;
}

bool cmp_2(quer a,quer b)
{
    return a.w>b.w;
}
int main()
{
    scanf("%i%i",&n,&m);

    for(int i=1;i<=m;i++)scanf("%i%i%i",&inp[i].u,&inp[i].v,&inp[i].d);

    scanf("%i",&q);

    for(int i=1;i<=q;i++)
        scanf("%i%i%i",&queries[i].type,&queries[i].u,&queries[i].w);

    for(int i=1;i<=q;i++)
        output[i]=-1;

    int block_size=2*sqrt(q);

    int le=1;

    while(le<=q)
    {
        int ri=min(q,le+block_size-1);

        pointer=0;

        for(int i=1;i<=n;i++)parent[i]=i,SZ[i]=1;

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

        pointer_queries=0;

        for(int i=le;i<=ri;i++)
            if(queries[i].type==1)keep[queries[i].u]=0;
            else
            {
                pointer_queries++;

                active_queries[pointer_queries]=queries[i];
                active_queries[pointer_queries].type=i;//the query's id
            }

        pointer_not_changed=0;

        pointer_changed=0;

        for(int i=1;i<=m;i++)
            if(keep[i])
            {
                pointer_not_changed++;
                not_changed[pointer_not_changed]=inp[i];
            }
            else
            {
                pointer_changed++;
                changed[pointer_changed]=i;

                additional[i]=inp[i].d;
            }

        sort(not_changed+1,not_changed+pointer_not_changed+1,cmp);

        sort(active_queries+1,active_queries+pointer_queries+1,cmp_2);

        for(int i=1;i<=pointer_queries;i++)
        {
            //activate forced
            while(pointer_not_changed>=1&&not_changed[pointer_not_changed].d>=active_queries[i].w)
            {
                my_merge(not_changed[pointer_not_changed].u,not_changed[pointer_not_changed].v);
                pointer_not_changed--;
            }

            int mem_pointer=pointer;
            //go for the not forced
            for(int j=le;j<=active_queries[i].type;j++)
                if(queries[j].type==1)
                    additional[queries[j].u]=queries[j].w;

            for(int p=1;p<=pointer_changed;p++)
            {
                if(additional[changed[p]]>=active_queries[i].w)
                {
                    my_merge(inp[changed[p]].u,inp[changed[p]].v);
                }
            }

            output[active_queries[i].type]=SZ[root(active_queries[i].u)];

            //remove the changes
            for(int p=1;p<=pointer_changed;p++)
                additional[changed[p]]=inp[changed[p]].d;

            while(mem_pointer<pointer)my_pop();
        }


        for(int i=le;i<=ri;i++)
            if(queries[i].type==1)
            {
                inp[queries[i].u].d=queries[i].w;
            }

        le=ri+1;
    }


    for(int i=1;i<=q;i++)
        if(output[i]!=-1)printf("%i\n",output[i]);
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:83:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=m;i++)scanf("%i%i%i",&inp[i].u,&inp[i].v,&inp[i].d);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
bridges.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&queries[i].type,&queries[i].u,&queries[i].w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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