Submission #555820

#	Time	Username	Problem	Language	Result	Execution time	Memory
555820		shahriarkhan	Bridges (APIO19_bridges)	C++14	100 / 100	2474 ms	9408 KiB

bridges

#include<bits/stdc++.h>
using namespace std ;

const int MX = 1e5 + 5 , block = 800 ;

struct query
{
    int type = 0 , vertice = 0 , edge = 0 , weight = 0 , idx = 0 ;
};

bool cmp(pair<int,int> &a , pair<int,int> &b)
{
    if(a.first!=b.first) return a.first > b.first ;
    return a.second > b.second ;
}

bool cmp1(query &a , query &b)
{
    if(a.weight!=b.weight) return a.weight > b.weight ;
    return a.idx < b.idx ;
}

vector<query> temp ;

vector<pair<int,int> > edges , edg ;

int ans[MX] , typ[MX] , val[MX] , vis[MX] , cur[MX] , temp_siz , n , m ;

struct dsu_rollback
{
    int u = 0 , v = 0 , siz_u = 0 , siz_v = 0 ;
};

struct dsu
{
    vector<int> par , siz ;
    stack<dsu_rollback> s ;
    void init(int n)
    {
        par = vector<int> (n+5,0) ;
        siz = vector<int> (n+5,0) ;
        for(int i = 1 ; i <= n ; ++i)
        {
            par[i] = i ;
            siz[i] = 1 ;
        }
    }
    int find_root(int a)
    {
        if(par[a]==a) return a ;
        return find_root(par[a]) ;
    }
    int union_edge(int a , int b)
    {
        int root_a = find_root(a) , root_b = find_root(b) ;
        if(root_a==root_b) return 0 ;
        if(siz[root_b]>siz[root_a]) swap(root_a,root_b) ;
        s.push({root_a,root_b,siz[root_a],siz[root_b]}) ;
        par[root_b] = root_a ;
        siz[root_a] += siz[root_b] ;
        return 1 ;
    }
    void rollback()
    {
        if(s.empty()) return ;
        dsu_rollback cur = s.top() ;
        s.pop() ;
        par[cur.u] = cur.u ;
        siz[cur.u] = cur.siz_u ;
        par[cur.v] = cur.v ;
        siz[cur.v] = cur.siz_v ;
    }
    int find_siz(int x)
    {
        return siz[find_root(x)] ;
    }
};

void process()
{
    dsu D ;
    D.init(n) ;
    vector<query> upd , out ;
    vector<int> unused ;
    unused.reserve(block) ;
    upd.reserve(block) ;
    out.reserve(block) ;
    for(query &q : temp)
    {
        if(q.type==1)
        {
            vis[q.edge] = 1 ;
            upd.emplace_back(q) ;
        }
        else out.emplace_back(q) ;
    }
    for(int i = 1 ; i <= m ; ++i)
    {
        if(vis[i]) unused.emplace_back(i) ;
    }
    sort(out.begin(),out.end(),cmp1) ;
    sort(edg.begin(),edg.end(),cmp) ;
    int cr = 0 ;
    for(query &q : out)
    {
        while((cr<m) && (edg[cr].first>=q.weight))
        {
            if(!vis[edg[cr].second]) D.union_edge(edges[edg[cr].second].first,edges[edg[cr].second].second) ;
            ++cr ;
        }
        int rollback = 0 ;
        for(query &p : upd)
        {
            if(p.idx>q.idx) break ;
            cur[p.edge] = p.weight ;
        }
        for(query &p : upd)
        {
            if(p.idx>q.idx) break ;
            if(cur[p.edge]>=q.weight)
            {
                rollback += D.union_edge(edges[p.edge].first,edges[p.edge].second) ;
                cur[p.edge] = -1 ;
            }
        }
        for(int &i : unused)
        {
            if(cur[i]) continue ;
            if(val[i]>=q.weight)
            {
                rollback += D.union_edge(edges[i].first,edges[i].second) ;
                cur[i] = -1 ;
            }
        }
        ans[q.idx] = D.find_siz(q.vertice) ;
        while(rollback)
        {
            D.rollback() ;
            --rollback ;
        }
        for(int &i : unused)
        {
            cur[i] = 0 ;
        }
    }
    for(query &q : upd)
    {
        val[q.edge] = q.weight ;
    }
    for(int i = 0 ; i < m ; ++i)
    {
        if(vis[edg[i].second])
        {
            edg[i].first = val[edg[i].second] , vis[edg[i].second] = 0 , cur[i] = 0 ;
        }
    }
    temp.clear() , temp_siz = 0 ;
}

int main()
{
    scanf("%d%d",&n,&m) ;
    edges.reserve(MX) ;
    edges.emplace_back(make_pair(0,0)) ;
    temp.reserve(block) ;
    for(int i = 1 ; i <= m ; ++i)
    {
        int a , b , d ;
        scanf("%d%d%d",&a,&b,&d) ;
        edges.emplace_back(make_pair(a,b)) ;
        val[i] = d ;
        edg.emplace_back(make_pair(val[i],i)) ;
    }
    int q ;
    scanf("%d",&q) ;
    for(int i = 1 ; i <= q ; ++i)
    {
        int type ;
        scanf("%d",&type) ;
        typ[i] = type ;
        if(type==1)
        {
            int b , r ;
            scanf("%d%d",&b,&r) ;
            query f = {1,0,b,r,i} ;
            temp.emplace_back(f) , ++temp_siz ;
        }
        else
        {
            int s , w ;
            scanf("%d%d",&s,&w) ;
            query f = {2,s,0,w,i} ;
            temp.emplace_back(f) , ++temp_siz ;
        }
        if(temp_siz==block) process() ;
    }
    if(temp_siz) process() ;
    for(int i = 1 ; i <= q ; ++i)
    {
        if(typ[i]==2) printf("%d\n",ans[i]) ;
    }
    return 0 ;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:162:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |     scanf("%d%d",&n,&m) ;
      |     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         scanf("%d%d%d",&a,&b,&d) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:175:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |     scanf("%d",&q) ;
      |     ~~~~~^~~~~~~~~
bridges.cpp:179:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |         scanf("%d",&type) ;
      |         ~~~~~^~~~~~~~~~~~
bridges.cpp:184:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |             scanf("%d%d",&b,&r) ;
      |             ~~~~~^~~~~~~~~~~~~~
bridges.cpp:191:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |             scanf("%d%d",&s,&w) ;
      |             ~~~~~^~~~~~~~~~~~~~

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