Submission #1263445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263445		kokoue	Bridges (APIO19_bridges)	C++20	0 / 100	2224 ms	7896 KiB

bridges

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn =5e4+5;
const int B=500;
int n,m,q;
struct Edge
{
    ll u,v,w;
};
struct Query
{
    int t,a,b,idx;
};
bool cmp(Edge e1,Edge e2)
{
    return e1.w<e2.w;
}
vector<Edge> edges;
vector<Query> qs;
int parent[maxn];
int sz[maxn];
int ans[maxn];
struct DSUret
{
    int paridx,szidx,szval;
};
stack<DSUret> st;
int findd(int u)
{
    if(parent[u]==0) return u;
    return findd(parent[u]);
}
bool unite(int uu,int vv)
{
    uu=findd(uu);
    vv=findd(vv);
    if(uu==vv) return 0;
    if(sz[uu]<sz[vv]) swap(uu,vv);
    st.push({vv,uu,sz[uu]});
    parent[vv]=uu;
    sz[uu]+=sz[vv];
    return 1;
}
void DoBlock(int l,int r)
{
    vector<int> forrem;
    vector<int> ups;
    vector<bool> is(m,0);
    vector<pair<int,int>> forsort;
    for(int i=l;i<=r;i++)
    {
        if(qs[i].t==1) ///update
        {
            is[qs[i].a]=1;
            ups.push_back(i);
        }
        if(qs[i].t==2) ///query
        {
            forsort.push_back({qs[i].b,-i});
        }
    }
    for(int i=0;i<m;i++)
    {
        if(!is[i]) forsort.push_back({edges[i].w,i+1});
    }
    sort(forsort.rbegin(),forsort.rend());
    for(auto e:forsort)
    {

        if(e.s>0)
        {
            unite(edges[e.s-1].u,edges[e.s-1].v);
            //printf("united edge %d %d weight %d\n",edges[e.s-1].u,edges[e.s-1].v,edges[e.s-1].w);
            continue;
        }
        int cntr=0;
        for(int i=0;i<ups.size();i++)
        {
            if(qs[ups[i]].idx<(-e.s))
            {
                if(qs[ups[i]].b>=e.f)
                {
                    //printf("1united edge %d\n",qs[ups[i]].a);
                    cntr+=unite(edges[qs[ups[i]].a].u,edges[qs[ups[i]].a].v);
                }
                continue;
            }
            if(edges[qs[ups[i]].a].w>=e.f)
            {
                //printf("2united edge %d\n",qs[ups[i]].a);
                cntr+=unite(edges[qs[ups[i]].a].u,edges[qs[ups[i]].a].v);
            }
        }
        //printf("did query %d for %d with cntr %d and ans %d\n",(-e.s),qs[-e.s].a,cntr,sz[findd(qs[-e.s].a)]);
        ans[-e.s]=sz[findd(qs[-e.s].a)];
        /*printf("before retrive: ");
        for(int i=1;i<=n;i++)
        {
            printf("{%d , %d} ",parent[i],sz[i]);
        }
        printf("\n");*/
        while(cntr && !st.empty())
        {
            cntr--;
            parent[st.top().paridx]=0;
            sz[st.top().szidx]=st.top().szval;
            st.pop();
        }
        /*printf("after retrive: ");
        for(int i=1;i<=n;i++)
        {
            printf("{%d , %d} ",parent[i],sz[i]);
        }
        printf("\n");*/
    }
    for(auto e:ups)
    {
        edges[qs[e].a].w=qs[e].b;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        parent[i]=0;
        sz[i]=1;
    }
    for(int i=0;i<m;i++)
    {
        int uu,vv,ww;
        cin>>uu>>vv>>ww;
        edges.push_back({uu,vv,ww});
    }
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int tt,aa,bb;
        cin>>tt>>aa>>bb;
        if(tt==1) aa--;
        qs.push_back({tt,aa,bb,i});
    }
    for(int i=0;i<q;i++)
    {
        DoBlock(i,min(i+B,q-1));
        i=min(i+B,q-1);
    }
    for(int i=0;i<q;i++)
    {
        if(qs[i].t==2) cout<<ans[i]<<"\n";
    }
}

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