Submission #375396

#	Time	Username	Problem	Language	Result	Execution time	Memory
375396		rrrr10000	Collapse (JOI18_collapse)	C++14	100 / 100	6578 ms	19272 KiB

collapse

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
using pl=pair<ll,ll>;
typedef vector<pl> 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));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
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]);}
#include "collapse.h"
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++;
        }
    }
};
vector<int> simulateCollapse(int n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P){
    ll C=T.size(),Q=W.size(),B=300;
    rep(i,C)if(X[i]>Y[i])swap(X[i],Y[i]);
    vp srtedge(C);
    vi edgeid(C);
    rep(i,C)srtedge[i]=pl(X[i],Y[i]);
    sort(all(srtedge));
    rep(i,C)edgeid[i]=lb(srtedge,pl(X[i],Y[i]));
	vvp query(C/B+1);
    rep(i,Q){
        query[W[i]/B].pb(P[i],i);
    }
    vector<int> ans(Q);
    rep(i,query.size())sort(all(query[i]));
    rep(i,query.size()){
        vb special(C,false);REP(j,i*B,min(C,(i+1)*B))special[edgeid[j]]=true;
        vi con(C);rep(j,i*B)con[edgeid[j]]=1-con[edgeid[j]];
        UF uf(n);
        vp s;rep(j,i*B)if(con[edgeid[j]]&&!special[edgeid[j]])s.pb(Y[j],X[j]);
        sort(all(s));
        ll w=0;
        vb used(C,false);
        for(auto x:query[i]){
            while(w!=s.size()&&s[w].fi<=x.fi){
                uf.merge(s[w].fi,s[w].se,0);
                w++;
            }
            for(int j=W[x.se];j>=i*B;j--)if(Y[j]<=x.fi&&!used[edgeid[j]]){
                if(!T[j])uf.merge(X[j],Y[j],1);
                used[edgeid[j]]=true;
            }
            REP(j,W[x.se]+1,min(C,(i+1)*B))if(Y[j]<=x.fi&&!used[edgeid[j]]&&con[edgeid[j]]){
                used[edgeid[j]]=true;
                uf.merge(X[j],Y[j],1);
            }
            ans[x.se]+=uf.cnt-(n-P[x.se]-1);
            REP(j,i*B,min(C,(i+1)*B))used[edgeid[j]]=false;
            uf.rollback();
        }
    }
    // outv(ans);
    rep(i,query.size())reverse(all(query[i]));
    rep(i,query.size()){
        vb special(C,false);REP(j,i*B,min(C,(i+1)*B))special[edgeid[j]]=true;
        vi con(C);rep(j,i*B)con[edgeid[j]]=1-con[edgeid[j]];
        UF uf(n);
        vp s;rep(j,i*B)if(con[edgeid[j]]&&!special[edgeid[j]])s.pb(X[j],Y[j]);
        rsort(s);
        vb used(C,false);
        ll w=0;
        for(auto x:query[i]){
            while(w!=s.size()&&s[w].fi>x.fi){
                uf.merge(s[w].fi,s[w].se,0);
                w++;
            }
            for(int j=W[x.se];j>=i*B;j--)if(X[j]>x.fi&&!used[edgeid[j]]){
                if(!T[j])uf.merge(X[j],Y[j],1);
                used[edgeid[j]]=true;
            }
            REP(j,W[x.se]+1,min(C,(i+1)*B))if(X[j]>x.fi&&!used[edgeid[j]]&&con[edgeid[j]]){
                used[edgeid[j]]=true;
                uf.merge(X[j],Y[j],1);
            }
            ans[x.se]+=uf.cnt-P[x.se]-1;
            REP(j,i*B,min(C,(i+1)*B))used[edgeid[j]]=false;
            uf.rollback();
        }
    }
    return ans;
}

Compilation message (stderr)

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:77: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]
   77 |             while(w!=s.size()&&s[w].fi<=x.fi){
      |                   ~^~~~~~~~~~
collapse.cpp:105: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]
  105 |             while(w!=s.size()&&s[w].fi>x.fi){
      |                   ~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35