Submission #784588

#	Time	Username	Problem	Language	Result	Execution time	Memory
784588		Denkata	Bridges (APIO19_bridges)	C++17	14 / 100	1386 ms	8184 KiB

bridges

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int crit = 1000;
const int maxn = 1e6+3;
int i,j,p,q,n,m,k,Q,br,d,new_w[maxn],ans[maxn+3];
int used[maxn];
struct Query
{
    int type;
    int first,second;
    int ind;
};
struct Edge
{
    int u,v,d;
};
vector <pair<int,int>> changed;
vector <Edge> v;
vector <Query> a,b;
bool fff(Query a,Query b)
{
    if(a.second!=b.second) return a.second>b.second;
    return a.type>b.type;
}
int par[maxn],sz[maxn];

int Find(int p)
{
    if(par[p]==p)
        return p;
    return Find(par[p]);
}

struct Roll_back
{
    int a,sza;
    int b,szb;
};
stack <Roll_back> st;
void Union(int p,int q,bool fl)
{
    p = Find(p);
    q = Find(q);

  //  cout<<p<<"  Union "<<q<<endl;
    if(p==q)return ;

    if(sz[p]>sz[q])swap(p,q);

    if(fl)
        st.push({p,sz[p],q,sz[q]});

    par[p] = q;
    sz[q] += sz[p];

}
void roll_back()
{
    while(!st.empty())
    {
        auto t = st.top();
        st.pop();
        par[t.a] = t.a;
        sz[t.a] = t.sza;
        par[t.b] = t.b;
        sz[t.b] = t.szb;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    v.push_back({0,0,0});///parser
    for(i=1; i<=m; i++)
    {
        cin>>p>>q>>k;
        v.push_back({p,q,k});
    }
    cin>>Q;
    for(i=1; i<=Q; i++)
    {
        cin>>p>>q>>k;
        b.push_back({p,q,k});
    }
    for(int ii=0; ii<Q; ii+=crit)
    {
        //cout<<ii<<" query "<<endl;
        int R = min(ii+crit-1,Q-1);
        for(int jj=ii; jj<=R; jj++)
            a.push_back({b[jj].type,b[jj].first,b[jj].second,jj});

        ++br;
        vector <Query> tek;
        changed.clear();
        tek.clear();

        for(auto i:a)
        {
            if(i.type==1)
            {
                p = i.first;
                q = i.second;
                new_w[p] = q;
               // cout<<p<<" changed "<<endl;
                changed.push_back({p,i.ind});
                used[p] = br;
            }
            else tek.push_back({-1,i.first,i.second,i.ind});
        }
        for(i=1; i<=m; i++)
        {
            if(used[i]!=br)
            {
              //  cout<<v[i].u<<" rebra "<<v[i].v<<" "<<v[i].d<<endl;
                tek.push_back({v[i].u,v[i].v,v[i].d});
            }
        }
        sort(tek.begin(),tek.end(),fff);
        for(i=0; i<=n+1; i++)
            par[i] = i,sz[i] = 1;
        for(auto i:tek)
        {
            if(i.type!=-1)
            {
                p = i.type;
                q = i.first;
            //    cout<<p<<" dobavqne "<<q<<endl;
                Union(p,q,0);
            }
            else
            {
                for(auto j:changed)
                {
             //       cout<<j.second<<" "<<v[j.first].d<<endl;
                    if((a[j.second].second>=i.second && j.second<i.ind) || (j.second>i.ind && v[j.first].d>=i.second))
                    {
                        Union(v[j.first].u,v[j.first].v,true);
                    }
                }
              //  cout<<i.ind<<" "<<sz[Find(i.first)]<<endl;
                ans[i.ind] = sz[Find(i.first)];
                roll_back();
            }
        }
        for(auto i:changed)
            v[i.first].d = a[i.second].second;
        a.clear();

    }
    for(i=0;i<Q;i++)
    {
        if(b[i].type==2)
            cout<<ans[i]<<endl;
    }

    return 0;
}
///if an edge is updated more than once during the same bucket query processing!

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