Submission #1326003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326003		I_FloPPed21	Bridges (APIO19_bridges)	C++20	59 / 100	3093 ms	5736 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
using namespace std;
const int N=5e4+5;
const int block=400;
struct dsu
{
    vector<int>rad;
    struct rollback
    {
        int a,val_a;
        int b,val_b;
    };
    stack<rollback>stiva;
    void init(int n)
    {
        rad.resize(n+1);
        for(int i=1; i<=n; i++)
            rad[i]=-1;
    }
    void clear(int n)
    {
        for(int i=1; i<=n; i++)
            rad[i]=-1;
        while(!stiva.empty())
            stiva.pop();
    }
    void roll(int siz)
    {
        while(siz)
        {
            rollback x=stiva.top();
            stiva.pop();
            siz--;
            rad[x.a]=x.val_a;
            rad[x.b]=x.val_b;
        }
    }
    int get(int x)
    {
        while(rad[x]>0)
        {
            x=rad[x];
            assert(x!=0);
        }
        return x;
    }

    void unite(int a,int b)
    {
        int x=get(a),y=get(b);
        stiva.push({x,rad[x],y,rad[y]});
        if(x==y)
            return;
        if(rad[x]>rad[y])
        {
            rad[y]+=rad[x];
            rad[x]=y;
        }
        else
        {
            rad[x]+=rad[y];
            rad[y]=x;
        }
    }
} structura;
int n,m,pret[2*N];
struct muchii
{
    int x,y,cost,id;
    bool operator <(const muchii &other)const
    {
        cost>other.cost;
    }
} edges[2*N];
bool used[N*2];
struct query
{
    int tip;
    int indice,cost;
} qr[2*N];

struct temp
{
    int insula,cost,moment;
    bool operator <(const temp &other)const
    {
        return cost>other.cost;
    }
};

bool operator_cmp(int x,int y)
{
    return edges[x].cost<edges[y].cost;
}
int rasp[2*N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    cin>>n>>m;
    structura.init(n);
    for(int i=1; i<=m; i++)
    {
        int a,b;
        cin>>edges[i].x>>edges[i].y>>edges[i].cost;
        edges[i].id=i;
    }
    int last=1;
    int q;
    cin>>q;
    for(int i=1; i<=q; i++)
    {
        cin>>qr[i].tip>>qr[i].indice>>qr[i].cost;
    }
    for(int i=1; i<=q; i++)
    {
        if((i==q)||(((i+1)/block)!=(i/block)))
        {
            structura.clear(n);
            vector<temp>batch;
            vector<pair<int,int>>indici_sqrt;//trebuie si costu vechi
            vector<int>indici;
            for(int j=last; j<=i; j++)
            {
                if(qr[j].tip==1)
                {
                    indici_sqrt.push_back({qr[j].indice,edges[qr[j].indice].cost});
                    used[qr[j].indice]=true;
                }
                else
                {
                    batch.push_back({qr[j].indice,qr[j].cost,j});
                }
            }
            for(int j=1; j<=m; j++)
            {
                if(!used[j])
                    indici.push_back(j);
            }
            sort(batch.begin(),batch.end());
            sort(indici.begin(),indici.end(), operator_cmp);
            int indice=indici.size()-1;
            for(auto u:batch)
            {
                while(indice>=0&&edges[indici[indice]].cost>=u.cost)
                {
                    muchii x=edges[indici[indice]];
                    structura.unite(x.x,x.y);
                    indice--;
                }
                int bck=0;
                for(auto k:indici_sqrt)
                {
                    edges[k.first].cost=k.second;
                }
                for(int j=last; j<=u.moment; j++)
                {
                    if(qr[j].tip==1)
                        edges[qr[j].indice].cost=qr[j].cost;
                }
                for(auto k:indici_sqrt)
                {
                    if(edges[k.first].cost>=u.cost)
                    {
                        structura.unite(edges[k.first].x,edges[k.first].y);
                        bck++;
                    }
                }
                //cout<<"huh"<<" "<<bck<<'\n';
                rasp[u.moment]=abs(structura.rad[structura.get(u.insula)]);
                structura.roll(bck);
            }
            for(int j=last; j<=i; j++)
                if(qr[j].tip==1)
                    edges[qr[j].indice].cost=qr[j].cost;

            for(auto k:indici_sqrt)
                used[k.first]=false;
            last=i+1;
        }
    }
    for(int i=1; i<=q; i++)
    {
        if(qr[i].tip==2)
            cout<<rasp[i]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'bool muchii::operator<(const muchii&) const':
bridges.cpp:76:5: warning: no return statement in function returning non-void [-Wreturn-type]
   76 |     }
      |     ^

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