Submission #784612

#	Time	Username	Problem	Language	Result	Execution time	Memory
784612		Denkata	Bridges (APIO19_bridges)	C++17	100 / 100	1806 ms	11904 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,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]);
}

stack <int> st,st2;
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);

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

}
void roll_back()
{
    while(!st.empty())
    {
        int t = st.top();
        st.pop();
        sz[par[t]]-=sz[t];
        par[t] = t;
    }
    while(!st2.empty())
    {
        p = st2.top();
        st2.pop();
        used[p] = 0;
    }
}

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;
               // 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(j=i.ind-1;j>=ii;j--)
                {
                    if(b[j].type==1 && used[b[j].first]!=-1)
                    {
                     //   cout<<"rebro predi query "<<b[j].first<<endl;
                        used[b[j].first] = -1;
                        st2.push(b[j].first);
                        if(b[j].second>=i.second)
                            Union(v[b[j].first].u,v[b[j].first].v,1);
                    }
                }
                for(j=i.ind+1;j<=R;j++)
                {

                    if(b[j].type==1 && used[b[j].first]!=-1)
                    {

                //        cout<<"rebro sled query "<<b[j].first<<endl;
                        if(v[b[j].first].d>=i.second)
                            Union(v[b[j].first].u,v[b[j].first].v,1);
                    }
                }
             //   cout<<i.first<<" "<<Find(i.first)<<" "<<sz[1]<<endl;
                ans[i.ind] = sz[Find(i.first)];
                roll_back();
            }
        }
        for(auto i:a)
            if(i.type==1)v[i.first].d = i.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!
///there is difference if an edge is updated before a query and after a query

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