Submission #1028075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028075		Vanio	Bridges (APIO19_bridges)	C++17	100 / 100	1853 ms	15800 KiB

bridges

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("avx2")  

#include<bits/stdc++.h>
    #define endl '\n'
    using namespace std;
    const int crit = 2000;
    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

Compilation message (stderr)

bridges.cpp:3:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("avx2")
      |                            ^
bridges.cpp:25:29: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   25 |     bool fff(Query a,Query b)
      |                             ^
bridges.cpp:32:19: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   32 |     int Find(int p)
      |                   ^
bridges.cpp:40:35: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   40 |     void Union(int p,int q,bool fl)
      |                                   ^
bridges.cpp:57:20: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   57 |     void roll_back()
      |                    ^
bridges.cpp:74:14: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   74 |     int main()
      |              ^

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