Submission #375489

#	Time	Username	Problem	Language	Result	Execution time	Memory
375489		rrrr10000	Bridges (APIO19_bridges)	C++14	100 / 100	2967 ms	17224 KiB

bridges

#include<bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define fi first
#define se second
#define pb emplace_back
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define dame(a) {out(a);return 0;}
#define rsort(a) {sort(all(a));reverse(all(a));}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> void outp(T p){printf("(%d,%d)",p.fi,p.se);cout<<'\n';}
template<class T> void outvp(T v){for(auto p:v)printf("(%d,%d)",p.fi,p.se);cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}

inline ll readll() {
    ll x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}
class UF{
    vi par,sz;
public:
    ll cnt;
    vp memo;
    UF(ll n){
        par=vi(n,-1);sz=vi(n,1);cnt=n;
    }
    ll root(ll i){if(par[i]==-1)return i;return root(par[i]);}
    void merge(ll a,ll b,bool flag){
        a=root(a);b=root(b);
        if(a==b)return;
        if(sz[a]>sz[b])swap(a,b);
        if(flag){memo.pb(a,par[a]);memo.pb(b,sz[b]);}
        par[a]=b;sz[b]+=sz[a];cnt--;
    }
    void rollback(){
        while(!memo.empty()){
            sz[memo.back().fi]=memo.back().se;memo.pop_back();
            par[memo.back().fi]=memo.back().se;memo.pop_back();
            cnt++;
        }
    }
    ll get(ll i){
        return sz[root(i)];
    }
};
int main(){
    ll n=readll(),m=readll(),B=800;
    vp edge(m);
    vi weight(m);
    rep(i,m){
        edge[i].fi=readll()-1;edge[i].se=readll()-1;weight[i]=readll();
    }
    ll Q=readll();
    vvi query(Q,vi(3));
    ll cnt=0;
    rep(i,Q){
        query[i][0]=readll();
        query[i][1]=readll()-1;
        query[i][2]=readll();
        if(query[i][0]==1)query[i][0]=-1;
        else query[i][0]=cnt++;
    }
    vi ans(cnt);
    rep(i,Q/B+1){
        UF uf(n);
        vb sp(m,false);
        vp q;
        REP(j,i*B,min((i+1)*B,Q)){
            if(query[j][0]==-1)sp[query[j][1]]=true;
            else q.pb(query[j][2],j);
        }
        rsort(q);
        vp s;rep(j,m)if(!sp[j])s.pb(weight[j],j);rsort(s);
        ll w=0;
        vb use(m,false);
        for(auto x:q){
            while(w!=s.size()&&s[w].fi>=x.fi){
                uf.merge(edge[s[w].se].fi,edge[s[w].se].se,0);
                w++;
            }
            for(int j=x.se-1;j>=i*B;j--)if(query[j][0]==-1&&!use[query[j][1]]){
                use[query[j][1]]=true;
                if(query[j][2]>=x.fi)uf.merge(edge[query[j][1]].fi,edge[query[j][1]].se,1);
            }
            REP(j,x.se+1,min((i+1)*B,Q))if(query[j][0]==-1&&!use[query[j][1]]&&weight[query[j][1]]>=x.fi)uf.merge(edge[query[j][1]].fi,edge[query[j][1]].se,1);
            ans[query[x.se][0]]=uf.get(query[x.se][1]);
            uf.rollback();
            REP(j,i*B,x.se)if(query[j][0]==-1)use[query[j][1]]=false;
        }
        REP(j,i*B,min((i+1)*B,Q))if(query[j][0]==-1)weight[query[j][1]]=query[j][2];
    }
    for(ll x:ans)out(x);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:100:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             while(w!=s.size()&&s[w].fi>=x.fi){
      |                   ~^~~~~~~~~~

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