Submission #1161621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161621		AlgorithmWarrior	Bridges (APIO19_bridges)	C++20	100 / 100	2981 ms	23120 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
int const SQRT=316;
int n,m;
struct EDGE{
    int u,v;
}edge[MAX];
int cost[MAX];
int q;
struct QUERY{
    int type,loc,w,ans;
}query[MAX];
int total;

void read(){
    cin>>n>>m;
    int i;
    for(i=1;i<=m;++i)
        cin>>edge[i].u>>edge[i].v>>cost[i];
    cin>>q;
    for(i=1;i<=q;++i)
        cin>>query[i].type>>query[i].loc>>query[i].w;
}

void normalize(){
    map<int,int>mep;
    int i;
    for(i=1;i<=m;++i)
        mep[cost[i]]=0;
    for(i=1;i<=q;++i)
        mep[query[i].w]=0;
    for(auto &[elem,zero] : mep)
        zero=++total;
    for(i=1;i<=m;++i)
        cost[i]=mep[cost[i]];
    for(i=1;i<=q;++i)
        query[i].w=mep[query[i].w];
}

struct node_rnk{
    int node,rk;
};

struct DSU{
    int tata[MAX],sz[MAX],rnk[MAX];
    stack<node_rnk>stv;
    void init(){
        int i;
        for(i=1;i<=n;++i){
            tata[i]=0;
            sz[i]=1;
            rnk[i]=1;
        }
    }
    int root(int nod){
        if(!tata[nod])
            return nod;
        return root(tata[nod]);
    }
    void uneste(int u,int v,bool trash){
        int ru=root(u);
        int rv=root(v);
        if(ru!=rv){
            if(rnk[ru]<rnk[rv])
                swap(ru,rv);
            if(trash)
                stv.push({rv,rnk[ru]});
            if(rnk[ru]==rnk[rv])
                ++rnk[ru];
            sz[ru]+=sz[rv];
            tata[rv]=ru;
        }
    }
    void roll_back(){
        while(!stv.empty()){
            auto [fiu,rkn] = stv.top();
            stv.pop();
            int nod=tata[fiu];
            rnk[nod]=rkn;
            sz[nod]-=sz[fiu];
            tata[fiu]=0;
        }
    }
}dsu;

bool uncertain[MAX];
int inter_edge[MAX];
int act_cost[SQRT+5][SQRT+5];
vector<int>upd[MAX],qry[MAX];

void solve(){
    int i;
    for(i=1;i<=q;i+=SQRT){
        int st,dr;
        st=i;
        dr=min(q,i+SQRT-1);
        int j;
        int id=0;
        for(j=st;j<=dr;++j)
            if(query[j].type==1 && !uncertain[query[j].loc]){
                uncertain[query[j].loc]=1;
                inter_edge[++id]=query[j].loc;
            }
        int ed;
        for(ed=1;ed<=id;++ed)
            act_cost[ed][0]=cost[inter_edge[ed]];
        for(ed=1;ed<=id;++ed)
            for(j=st;j<=dr;++j)
                if(query[j].type==1 && query[j].loc==inter_edge[ed])
                    act_cost[ed][j-st+1]=query[j].w;
                else
                    act_cost[ed][j-st+1]=act_cost[ed][j-st];
        for(j=1;j<=m;++j)
            if(!uncertain[j])
                upd[cost[j]].push_back(j);
        for(j=st;j<=dr;++j)
            if(query[j].type==2)
                qry[query[j].w].push_back(j);
        dsu.init();
        for(j=total;j;--j){
            for(auto edg : upd[j])
                dsu.uneste(edge[edg].u,edge[edg].v,0);
            for(auto poz : qry[j]){
                for(ed=1;ed<=id;++ed)
                    if(act_cost[ed][poz-st+1]>=query[poz].w)
                        dsu.uneste(edge[inter_edge[ed]].u,edge[inter_edge[ed]].v,1);
                query[poz].ans=dsu.sz[dsu.root(query[poz].loc)];
                dsu.roll_back();
            }
        }
        for(ed=1;ed<=id;++ed)
            cost[inter_edge[ed]]=act_cost[ed][dr-st+1];
        for(j=1;j<=m;++j)
            uncertain[j]=0;
        for(j=1;j<=total;++j){
            upd[j].clear();
            qry[j].clear();
        }
    }
}

void write(){
    int i;
    for(i=1;i<=q;++i)
        if(query[i].type==2)
            cout<<query[i].ans<<'\n';
}

int main()
{
    read();
    normalize();
    solve();
    write();
    return 0;
}

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